Introversion
Description
You run a restaurant called Taste Of Pacific Cuisine (TOPC). This weekend, you will be hosting a large banquet that caters a sizable group of guests. Your chef designed $n$ types of dishes. To ensure every guest a chance to taste each type of the dishes, you plan to prepare two dishes per dish type. (Hence there are a total of $2n$ dishes at the banquet.)
There is a very long table in your restaurant, and you plan to exhibit all $2n$ dishes in a line on this table all at once. Not surprisingly, the length of the table fits exactly $2n$ dishes. As a considerate host, you plan to make sure that no two dishes of the same type are laying on the table together — this allows a variety of choices for introversion individuals who prefer not to wander around.
Now, some dishes have already been brought to the table. Can you quickly count the number of ways to place the remaining dishes such that no two dishes of the same type are placing together? You must compute this number quickly so you can give an introductory overview to your kitchen staff on how to place the remaining dishes — that's what you call an intro version. Since the number of ways could be large, it suffices to output the answer modulo $10^9+7$.
The first line contains an integer $T$, denoting the number of test cases. For each test case, the first line contains an integer $n$. The second line contains $2n$ integers $x_1, x_2, \cdots, x_{2n}$ separated by a space. If $x_i=0$ it means that the $i$-th position on the table is empty. Otherwise, $x_i$ will be an integer ranges between $1$ and $n$ denoting the type of the dish. It is guaranteed that for each dish type $k\in \{1, 2, \ldots, n\}$, $k$ occurs at most twice in the input sequence. In addition, if $k$ does occur two times in the sequence, these two numbers will not be neighboring.
- $1\le T\le 20$.
- $2\le n\le 100$.
- $0\le x_i\le n$.
Output the number of valid ways to serve all the remaining dishes, modulo $10^9+7$.
Input
The first line contains an integer $T$, denoting the number of test cases. For each test case, the first line contains an integer $n$. The second line contains $2n$ integers $x_1, x_2, \cdots, x_{2n}$ separated by a space. If $x_i=0$ it means that the $i$-th position on the table is empty. Otherwise, $x_i$ will be an integer ranges between $1$ and $n$ denoting the type of the dish. It is guaranteed that for each dish type $k\in \{1, 2, \ldots, n\}$, $k$ occurs at most twice in the input sequence. In addition, if $k$ does occur two times in the sequence, these two numbers will not be neighboring.
- $1\le T\le 20$.
- $2\le n\le 100$.
- $0\le x_i\le n$.
Output
Output the number of valid ways to serve all the remaining dishes, modulo $10^9+7$.
3
2
1 2 0 0
2
1 0 2 0
5
0 0 0 0 0 1 2 3 4 5
1
0
96