[AdditionalFile5685.zip](file://AdditionalFile5685.zip?type=additional_file)

#5685. 「PA 2026」Multi-brydż

标签: 传统 | 时间限制: 1000 ms | 内存限制: 1024 MiB |

题目描述

题目译自 PA 2026 Runda 4 Multi-brydż

多人桥牌由两个队伍（我们称之为 Potykacze 和 Algorytmicy）进行，每队由 $n$ 名玩家组成。玩家坐在圆桌旁，位置编号从 $1$ 到 $2n$。奇数位置坐的是 Potykacze 队的玩家，偶数位置坐的是 Algorytmicy 队的玩家。游戏使用 $4n$ 张牌，点数为 $1, 2, 3, \ldots, 4n$。游戏开始时，每位玩家手中持有两张牌。每位玩家都知道其他玩家手中的牌。

游戏分为两轮。在第一轮中，随机位置 $i$ 的玩家首先行动，打出一张手中的牌。随后，位置为 $(i \bmod 2n)+1$、$(i+1 \bmod 2n)+1$ 直至 $(i+2n-2 \bmod 2n)+1$ 的玩家依次打出一张牌。打出最高点数牌的玩家所在队伍获得 $1$ 分。在第二轮中，所有玩家打出手中剩余的一张牌。同样地，打出最高点数牌的玩家所在队伍获得 $1$ 分。

输入给出一个长度为 $2n$ 的整数序列 $a_{1}, \ldots, a_{2n}$，描述了游戏结果。具体来说，对于 $1 \leq i \leq 2n$，如果位置 $i$ 的玩家先手且所有玩家策略最优，则 Algorytmicy 队将获得恰好 $a_{i}$ 分。

请计算出有多少种不同的牌分配方案符合这些得分结果，并将结果对 $10^{9}+7$ 取模。如果对于任意位置 $i$ 和牌面值 $x$，某个方案中该位置的玩家拥有值为 $x$ 的牌而另一个方案中没有，则认为这两个方案是不同的。

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

输入格式

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

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

第二行包含一个长度为 $2n$ 的整数序列 $a_{1}, \ldots, a_{2n}$ $(0 \leq a_{i} \leq 2)$；值 $a_{i}$ 表示如果位置 $i$ 的玩家先手，Algorytmicy 队将获得的得分。

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

输出格式

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

样例

输入

4
2
1010
1
02
3
100110
7
111111111111111111
2
00110
111111111111111

输出

24
0
0
256223893

数据范围与提示

在第一个测试用例中，符合给定得分序列的一个牌分配方案是：第一个玩家拥有牌 $4$ 和 $6$，第二个玩家拥有 $3$ 和 $7$，第三个拥有 $2$ 和 $8$，第四个拥有 $1$ 和 $5$。

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