Congress of Young Enthusiasts

Interview

Time limit2sMemory limit256 MB

Summary

Count the ways to seat n mathematicians and n philosophers in 2n chairs of types 1, 2, and 3, modulo 10^9 + 7.

Level: Medium4 of 10
Topics: Combinatorics, Math
Solved: No attempts yet

Problem

On February 37, 3015, the Congress of Young Enthusiasts of Mathematics and Philosophy was declared open. Each of the $n$ countries sent one mathematician and one philosopher. A meeting with all participants will take place in two hours, and the organizers have not yet decided how to seat them. The meeting hall has $2n$ chairs in a row. There are three types of chairs: a type 1 chair can seat only a mathematician, a type 2 chair can seat only a philosopher, and a type 3 chair can seat any participant.

Input

The first line contains one positive integer $t$ , the number of tests. Each test is described by two lines. The first line contains one integer $n$ , the number of countries. The second line contains $2n$ positive integers from 1 to 3, where the $i$ -th number gives the type of the $i$ -th chair. The sum of $n$ over all tests does not exceed 100.

Output

For each test, print the number of ways to seat the participants, modulo $10^9 + 7$ .

Examples1

Example 1
Input
```
2
2
3 3 3 3
2
1 1 1 1
```
Expected output
```
8
0
```