Problem Statement

In Multi-Bridge, two teams are playing (let us call them Potykacze and Algorytmicy), each consisting of n players.

The players sit around a round table, at positions numbered from 1 to 2n. Players from Potykacze sit at odd-numbered positions, while players from Algorytmicy sit at even-numbered positions. The game uses 4n cards with values 1, 2, 3, ..., 4n.

At the beginning of the game, each player holds exactly two of these cards. Every player knows which cards all other players have.

The game consists of two tricks.

In the first trick, the player at some starting position plays first by placing one of their two cards on the table. Then the remaining players play, in cyclic order around the table, each placing one of their two cards on the table. The team of the player who placed the card with the highest value scores 1 point.

In the second trick, every player places their remaining card on the table. Again, the team of the player who placed the card with the highest value scores 1 point.

You are given a sequence of 2n integers (a_1, a_2, \dots, a_{2n}), describing the result of the game depending on which player moves first. More precisely, for each (1 \le i \le 2n), if the player at position (i) moves first and all players play optimally, then the team Algorytmicy scores exactly (a_i) points.

Determine the number of different card distributions consistent with these results, and print this number modulo (10^9 + 7).

Two card distributions are considered different if there exists some position (i) and some card value (x) such that the player at position (i) holds a card of 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 input contains a single integer t ((1 \le t \le 1000)), the number of test cases.

For each test case:

• The first line contains one integer n ((1 \le n \le 10^6)), the number of players in each team.
• The second line contains 2n integers (a_1, a_2, \dots, a_{2n}) ((0 \le a_i \le 2)). The value (a_i) denotes the number of points scored by team Algorytmicy if the player at position (i) moves first.

The sum of all values of n over all test cases does not exceed (10^6).

Output

For each test case, output one line containing a single integer: the number of card distributions consistent with the given sequence, modulo (10^9 + 7).

Example

Input

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

24
0
0
256223893

Explanation

In the first test case, one example of a card distribution consistent with the given sequence is:

• player 1 has cards 4 and 6,
• player 2 has cards 3 and 7,
• player 3 has cards 2 and 8,
• player 4 has cards 1 and 5.

In the second and third test cases, there is no card distribution consistent with the given sequence.