Introversion

Time limit3sMemory limit1024 MB

Summary

Given a row of 2n slots with some dishes fixed, count the ways to fill the empty slots so each type appears twice and no two equal types are adjacent, modulo 1e9+7.

Level: Hard8 of 10
Topics: Dynamic programming, Combinatorics, Implementation
Solved: No attempts yet

Problem

You run a restaurant called Taste Of Pacific Cuisine (TOPC). This weekend you will host a large banquet for a sizable group of guests. Your chef designed $n$ types of dishes. So that every guest can taste each type, you plan to prepare two dishes per type, for a total of $2n$ dishes at the banquet.

The table is very long and fits exactly $2n$ dishes in a single line. You plan to set out all $2n$ dishes at once. No two dishes of the same type may sit next to each other, which gives introverted guests who prefer not to wander around a fair choice of dishes nearby.

Some dishes are already on the table. Count the number of ways to place the remaining dishes so that no two dishes of the same type are adjacent. Call this the intro version of the seating problem. Since the count can be large, output it modulo $10^9+7$ .

Input

The first line contains an integer $T$ , the number of test cases. Each test case starts with an integer $n$ . The next line contains $2n$ integers $x_1, x_2, \cdots, x_{2n}$ separated by spaces. If $x_i=0$ , the $i$ -th position on the table is empty. Otherwise, $x_i$ is an integer between $1$ and $n$ giving the dish type. It is guaranteed that each type $k \in \{1,2,\dots,n\}$ appears at most twice in the input. If a type appears twice, the two occurrences are not adjacent.

Output

For each test case, output the number of valid ways to place all the remaining dishes, modulo $10^9+7$ .

Constraints

$1 \le T \le 20$

$2 \le n \le 100$

$0 \le x_i \le n$

Examples1

Example 1

Input

3
2
1 2 0 0
2
1 0 2 0
5
0 0 0 0 0 1 2 3 4 5

Expected output

1
0
96