U230600 完美与奇偶性

dbxxx 有 $2n$ 个数 $a_1 \sim a_{2n}$，初始值均为 $0$. 对这 $2n$ 个数可以**进行 $n$ 次操作**，每次操作可以选定一个区间 $[l, r](1 \le l < r \le 2n)$，使得**位于区间 $[l, r]$ 中的数全部自增 $1$**。具体地，一次操作 $[l, r]$，可以使得 $\forall l \le i \le r, a_i \gets a_i +1$。 dbxxx 希望这些操作满足以下条件： - $n$ 次操作中表示 $l$，$r$ 的 $2n$ 个数**恰好**为 $1 \sim 2n$ 的一个排列； - $n$ 次操作后，$\forall 1 \le i \le 2n,a_i \bmod 2 = b_i$（$b$ 数组会在输入中给定）。 旁边的 xrk 神仙很快便轻松地给出了一种方案。dbxxx 想知道 xrk 是如何操作的，但 xrk 想先让 dbxxx 回答一个问题：xrk 的这 $n$ 次操作有**多少种可能的情况**？ dbxxx 当然不会，你赶紧给我帮他。 **由于答案可能很大，你应该输出的是答案对 $10^9 +7$ 取模的结果。** **注意，仅顺序不同的多次操作算一种情况，如 $[1, 2], [3, 4]$ 和 $[3, 4], [1, 2]$ 算作一种情况。**

**本题有多组数据。** 第一行，一个正整数 $T$，表示数据组数。 对于每一组数据，第一行为一个正整数 $n$，含义如题面所示。 第二行为 $2n$ 个用空格隔开的整数 $b_i$，含义如题面所示。

对于每一组数据，输出一行，表示 xrk 的 $n$ 次操作有多少种可能的情况。

## 样例解释 此处仅解释样例 #1。 第一组数据： 两种情况分别为 $[1, 3], [2, 4]$ 和 $[1,4], [2, 3]$。 以第一种情况举例分析： - 操作中的所有 $l$，$r$ 是 $1 \sim 4$ 的一个全排列，因此满足条件 $1$； - 操作后 $a$ 数组的值为 $[1, 2, 2, 1]$，满足 $\forall 1 \le i \le 2n,a_i \bmod 2 = b_i$，因此满足条件 $2$。 因此这种情况是合法的。 第二种情况略。 第二组数据仅以一种情况为例举例分析： - $[1, 4], [2, 8], [3, 5], [6, 7]$ - 操作中的所有 $l$，$r$ 是 $1 \sim 8$ 的一个全排列，因此满足条件 $1$； - 操作后 $a$ 数组的值为 $[1, 2, 3, 3, 2, 2, 2, 1]$，满足 $\forall 1 \le i \le 2n,a_i \bmod 2 = b_i$，因此满足条件 $2$。 ## 数据约束与规定 - 对于 $20 \%$ 的数据，$1 \le n \le 3$； - 对于 $40 \%$ 的数据，$1 \le n \le 7$； - 对于 $70 \%$ 的数据，$1 \le n \le 2 \times 10^3$； - 对于 $100 \%$ 的数据，$1 \le T \le 10, 1 \le n \le 10^5, b_i \in \{0, 1\}$。