Problem Description

In the game of multiple bridge, there are two teams (we call them the "Keban-zhe" and the "Algorithmists"), each consisting of $n$ players.

The players sit around a round table, with positions numbered from $1$ to $2n$. The Keban-zhe sit in odd positions, and the Algorithmists sit in even positions. The game uses $4n$ cards with face values $1, 2, 3, \ldots, 4n$. Each player holds two of these cards at the start of the game. Every player knows the cards held by all other players.

The game consists of two rounds. In the first round, the player at a random position $i$ plays first and plays one of their two cards. Then, the players at positions $(i \bmod 2n) + 1,\ (i+1 \bmod 2n) + 1,\ \ldots,\ (i+2n-2 \bmod 2n) + 1$ play in order (each plays one of their two cards). The team of the player who played the highest-valued card gets $1$ point. In the second round, all players play their remaining card. Again, the team of the player who played the highest-valued card gets $1$ point.

The input gives a sequence of $2n$ integers $a_1, \ldots, a_{2n}$ describing the relationship between the game outcome and the starting player. Specifically, for $1 \le i \le 2n$, if the player at position $i$ plays first and all players use optimal strategies, then the Algorithmists team gets exactly $a_i$ points.

Compute the number of different dealing arrangements consistent with the given outcome sequence, and output this number modulo $10^9 + 7$. If for some position $i$ and some card value $x$, the player at position $i$ holds the card with value $x$ in one arrangement but does not hold it in another, then these two dealing arrangements are considered different.

You need to solve this problem for $t$ independent test cases.

Input Format

The first line contains an integer $t$ ($1 \le t \le 1000$), the number of test cases.

For each test case, the first line contains an integer $n$ ($1 \le n \le 10^6$), the number of players on each team.

The second line contains a sequence of $2n$ integers $a_1, \ldots, a_{2n}$ ($0 \le a_i \le 2$). The value $a_i$ indicates the number of points the Algorithmists team gets when the player at position $i$ plays first.

The sum of $n$ over all test cases does not exceed $10^6$.

Output Format

Output $t$ lines. The $j$-th line should contain one integer: the number of dealing arrangements consistent with the outcome sequence of the $j$-th test case, modulo $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

Hint

Sample Explanation

In the first test case, one dealing arrangement consistent with the given input outcome sequence is: the first player holds cards $4$ and $6$, the second player holds $3$ and $7$, the third player holds $2$ and $8$, and the fourth player holds $1$ and $5$.

In the second and third test cases, there is no dealing arrangement consistent with the given input outcome sequence.

Translated by ChatGPT 5