题目描述

你经营着一家名为 Taste Of Pacific Cuisine (TOPC) 的餐厅。本周末，你将承办一场大型宴会，招待众多宾客。你的厨师设计了 $n$ 种菜品。为了确保每位宾客都能品尝到每种菜品，你计划为每种菜品准备 两道。（因此宴会上共有 $2n$ 道菜。）

餐厅里有一张很长的桌子，你打算将所有 $2n$ 道菜一次性地在桌子上排成一行展示。不出所料，桌子的长度恰好可以摆放 $2n$ 道菜。作为一位体贴的主人，你希望确保同一类型的菜不会有两道相邻摆放——这样可以为那些不喜欢四处走动的内向宾客提供多样化的选择。

现在，有些菜已经摆上了桌子。你能快速计算出摆放剩余菜品的方式数量，使得同一类型的菜不会有两道相邻吗？你必须快速计算出这个数字，以便向厨房员工介绍如何摆放剩余菜品——这就是你所说的“介绍版”。由于方案数可能很大，只需输出答案对 $10^9 + 7$ 取模的结果。

输入格式

第一行包含一个整数 $T$，表示测试用例的数量。对于每个测试用例，第一行包含一个整数 $n$。第二行包含 $2n$ 个空格分隔的整数 $x_1, x_2, \cdots, x_{2n}$。如果 $x_i = 0$，表示桌子上第 $i$ 个位置为空；否则，$x_i$ 是 $1$ 到 $n$ 之间的整数，表示该位置菜品的类型。保证对于每种菜品类型 $k \in \{1, 2, \dots, n\}$，$k$ 在输入序列中最多出现两次。此外，如果 $k$ 在序列中出现了两次，这两个数不会相邻。

输出格式

输出摆放所有剩余菜品的合法方案数，对 $10^9 + 7$ 取模。

3
2
1 2 0 0
2
1 0 2 0
5
0 0 0 0 0 1 2 3 4 5

1
0
96

提示

• $1 \le T \le 20$
• $2 \le n \le 100$
• $0 \le x_i \le n$

翻译由 DeepSeek V3.2 完成