你经营着一家名为 Taste Of Pacific Cuisine (TOPC) 的餐厅。这个周末，你将举办一场大型宴会，接待大批宾客。你的主厨设计了 $n$ 种菜品。为了确保每位宾客都有机会品尝到每种菜品，你计划每种菜品准备两份。（因此，宴会上总共有 $2n$ 份菜品。）

你的餐厅里有一张很长的桌子，你计划将所有 $2n$ 份菜品在这张桌子上排成一排同时展出。不出所料，桌子的长度正好可以容纳 $2n$ 份菜品。作为一位贴心的主人，你计划确保桌上没有任意两份相同类型的菜品相邻摆放——这为那些不喜欢到处走动的内向人士提供了多样化的选择。

现在，一些菜品已经摆放在桌子上了。你能快速计算出摆放剩余菜品的方法数，使得没有任意两份相同类型的菜品相邻摆放吗？你必须快速计算出这个数量，以便向你的厨房员工简要介绍如何摆放剩余的菜品——这就是你所谓的“内向版本”（intro version）。由于方法数可能很大，你只需要输出答案模 $10^9 + 7$ 的结果。

输入格式

第一行包含一个整数 $T$，表示测试用例的数量。对于每个测试用例：

第一行包含一个整数 $n$。

第二行包含 $2n$ 个由空格分隔的整数 $x_1, x_2, \dots, x_{2n}$。如果 $x_i = 0$，表示桌子上的第 $i$ 个位置是空的。否则，$x_i$ 将是一个介于 $1$ 和 $n$ 之间的整数，表示菜品的类型。

保证对于每种菜品类型 $k \in \{1, 2, \dots, n\}$，$k$ 在输入序列中最多出现两次。此外，如果 $k$ 在序列中确实出现了两次，这两个数不会相邻。

输出格式

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

数据范围

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

样例

输入样例 1

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

输出样例 1

1
0
96