Problem Statement

Two teams (let's call them Potykacze and Algorytmicy) play a game of multi-bridge, each consisting of $n$ players. The players sit at a round table at positions numbered from $1$ to $2n$. Potykacze sit at odd positions, and Algorytmicy sit at even positions. The game is played using $4n$ cards with values $1, 2, 3, \dots, 4n$. At the beginning of the game, each player has two of these cards. Each player knows which cards the other players have.

The game consists of two tricks. In the first trick, the player at a random position $i$ moves first, playing one of their two cards onto the table. Then, the players at positions $(i \pmod{2n}) + 1$, $(i+1 \pmod{2n}) + 1$, up to $(i+2n-2 \pmod{2n}) + 1$ move in sequence, each playing one of their two cards onto the table. The team of the player who played the card with the highest value wins one point. In the second trick, all players play their remaining card onto the table. Again, the team of the player who played the card with the highest value wins one point.

You are given a sequence of $2n$ integers $a_1, \dots, a_{2n}$, which describe the game results depending on which player moved first. Specifically, for $1 \le i \le 2n$, if the player at position $i$ moves first and all players play optimally, the Algorytmicy team scores exactly $a_i$ points.

Determine the number of different card distributions that are consistent with these results, and output the remainder of this number divided by $10^9 + 7$. Two card distributions are different if, for any position $i$ and value $x$, the player at position $i$ has a card with value $x$ in one distribution but not in the other.

You must solve this problem for $t$ independent test cases.

Input

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

The first line of each test case description contains a single integer $n$ ($1 \le n \le 10^6$), representing the number of players in each team.

The second line contains a sequence of $2n$ integers $a_1, \dots, a_{2n}$ ($0 \le a_i \le 2$); the value $a_i$ denotes the number of points the Algorytmicy team will score if the player at position $i$ moves first.

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

Output

The output should contain $t$ lines. The $j$-th line should contain a single integer representing the remainder of the number of card distributions consistent with the sequence of results given in the $j$-th test case when divided by $10^9 + 7$.

Examples

Input 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

Output 1

24
0
0
256223893

Note

In the first test case, an example card distribution consistent with the input sequence of results is one where the first player has cards 4 and 6, the second player has 3 and 7, the third player has 2 and 8, and the fourth player has 1 and 5. In the second and third test cases, there is no card distribution consistent with the given sequence of results.