“多桥牌”游戏由两支队伍（分别称为 Potykacze 和 Algorytmicy）进行，每支队伍各有 $n$ 名玩家。玩家围坐在一张圆桌旁，位置编号从 $1$ 到 $2n$。奇数位置坐的是 Potykacze 队的玩家，偶数位置坐的是 Algorytmicy 队的玩家。游戏使用 $4n$ 张牌，牌面值为 $1, 2, 3, \dots, 4n$。游戏开始时，每位玩家持有其中的两张牌。每位玩家都知道其他所有玩家手中的牌。

游戏由两轮（trick）组成。在第一轮中，位于随机位置 $i$ 的玩家首先出牌，将他手中的两张牌中的一张放到桌上。随后，位置为 $(i \pmod{2n}) + 1, (i+1 \pmod{2n}) + 1, \dots, (i+2n-2 \pmod{2n}) + 1$ 的玩家依次出牌（每人出一张）。打出最大牌值的玩家所在的队伍获得一分。在第二轮中，所有玩家打出他们剩余的最后一张牌。同样，打出最大牌值的玩家所在的队伍获得一分。

输入包含 $2n$ 个整数 $a_1, \dots, a_{2n}$，描述了游戏结果。具体而言，对于 $1 \le i \le 2n$，如果位置 $i$ 的玩家先手出牌，且所有玩家均采取最优策略，则 Algorytmicy 队将获得恰好 $a_i$ 分。

请计算符合这些结果的牌局分配方案总数，并输出该数值对 $10^9 + 7$ 取模后的结果。如果对于任意位置 $i$ 和牌值 $x$，在两种方案中位置 $i$ 的玩家持有的牌不同，则认为这两个方案是不同的。

你需要解决 $t$ 个独立的测试用例。

输入格式

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

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

第二行包含 $2n$ 个整数 $a_1, \dots, a_{2n}$ ($0 \le a_i \le 2$)，其中 $a_i$ 表示如果位置 $i$ 的玩家先手出牌，Algorytmicy 队将获得的分数。

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

输出格式

输出 $t$ 行。第 $j$ 行应包含一个整数，表示第 $j$ 个测试用例中符合给定结果序列的牌局分配方案数对 $10^9 + 7$ 取模后的结果。

样例

输入格式 1

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

输出格式 1

24
0
0
256223893

说明

在第一个测试用例中，符合输入结果序列的一种牌局分配方案是：第一位玩家持有牌 4 和 6，第二位玩家持有 3 和 7，第三位玩家持有 2 和 8，第四位玩家持有 1 和 5。

在第二个和第三个测试用例中，不存在符合给定结果序列的牌局分配方案。