题目描述

在多重桥牌游戏中，两支队伍（我们称之为"磕绊者"和"算法师"）各由 $n$ 名玩家组成。 玩家围坐于一张圆桌旁，位置编号为 $1$ 到 $2n$。奇数位置坐的是磕绊者，偶数位置坐的是算法师。游戏使用 $4n$ 张牌，牌面值为 $1, 2, 3, \ldots, 4n$。 每位玩家在游戏开始时持有其中两张牌。每位玩家均知道其余所有玩家手中的牌。

游戏由两局组成。在第一局中，位于随机位置 $i$ 的玩家首先出牌，将其两张牌中的一张打出。 随后，位置依次为 $(i \mod 2n) + 1,\ (i+1 \mod 2n) + 1,\ \ldots,\ (i+2n-2 \mod 2n) + 1$ 的玩家依次出牌（各打出两张牌中的一张）。打出牌面值最高的牌的玩家所在队伍得一分。在第二局中，所有玩家打出各自剩余的那张牌。再次地，打出牌面值最高的牌的玩家所在队伍得一分。

输入将给出一个由 $2n$ 个整数组成的序列 $a_1, \ldots, a_{2n}$，用于描述游戏结果与首位出牌玩家的对应关系，具体而言：对于 $1 \le i \le 2n$，若位于位置 $i$ 的玩家首先出牌，且所有玩家均采取最优策略，则算法师队伍恰好得 $a_i$ 分。

请求出与上述结果序列相符的不同发牌方案数，并输出该数除以 $10^9 + 7$ 的余数。若对于某个位置 $i$ 和某个牌面值 $x$，位于位置 $i$ 的玩家在其中一种方案中持有牌面值为 $x$ 的牌，而在另一种方案中不持有，则称这两种方案不同。

你需要对 $t$ 个相互独立的测试用例求解此问题。

输入格式

输入的第一行包含一个整数 $t$（$1 \le t \le 1000$），表示测试用例的数量。

每个测试用例描述的第一行包含一个整数 $n$（$1 \le n \le 10^6$），表示每支队伍中的玩家人数。

第二行包含 $2n$ 个整数组成的序列 $a_1, \ldots, a_{2n}$（$0 \le a_i \le 2$）；$a_i$ 的值表示当位于位置 $i$ 的玩家首先出牌时，算法师队伍所得的分数。

所有测试用例的 $n$ 之和不超过 $10^6$。

输出格式

输出应包含 $t$ 行。第 $j$ 行应包含一个整数，表示与第 $j$ 个测试用例中给定结果序列相符的发牌方案数除以 $10^9 + 7$ 的余数。

4
2
1 0 1 0
1
0 2
3
1 0 0 1 1 0
7
1 1 1 1 1 1 1 1 1 1 1 1 1 1

24
0
0
256223893

提示

样例说明

在第一个测试用例中，一种与给定输入结果序列相符的发牌方案如下：第一位玩家持有牌 $4$ 和 $6$，第二位玩家持有 $3$ 和 $7$，第三位玩家持有 $2$ 和 $8$，第四位玩家持有 $1$ 和 $5$。

在第二和第三个测试用例中，不存在与给定输入结果序列相符的发牌方案。