Read problem statements in [Hindi], [Bengali], [Mandarin Chinese], [Russian], and [Vietnamese] as well.

Chefina likes prefix and suffix sums, so Chef decided to give some to her as her birthday present. He created a sequence $a_{1}, a_{2}, \ldots, a_{N}$ and calculated its prefix sums $pre_{1}, pre_{2}, \ldots, pre_{N}$ (for each valid $i$, $pre_{i}$ is the sum of the first $i$ elements of $a$) and suffix sums $suf_{1}, suf_{2}, \ldots, suf_{N}$ (for each valid $i$, $suf_{i}$ is the sum of the last $i$ elements of $a$). He arranged the elements of these sequences in a gift box and went to Chefina's home.

When Chefina opened the gift box, she found out that all the elements got shuffled when Chef was carrying the box. For each element, it is now impossible to determine if it belonged to the sequence $pre$ or $suf$ and what its index in the correct sequence was. The only thing we know is a sequence $x_{1}, x_{2}, \ldots, x_{2N}$, which contains all the elements of the sequences $pre$ and $suf$, in no particular order.

Chefina is now curious about the number of initial sequences $a$ which Chef could have chosen, such that it is possible to obtain $x$ by shuffling the prefix and suffix sums of $a$. Help Chefina find this number. Since it could be very large, compute it modulo $1,000,000,007$.

------ Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first line of each test case contains a single integer $N$.
The second line contains $2N$ space-separated integers $x_{1}, x_{2}, \ldots, x_{2N}$.

------ Output ------
For each test case, print a single line containing one integer ― the number of possible initial sequences modulo $1,000,000,007$.

------ Constraints ------
$1 ≤ T ≤ 10^{6}$
$1 ≤ N ≤ 10^{5}$
$|x_{i}| ≤ 10^{9}$ for each valid $i$
the sum of $N$ over all test cases does not exceed $2 \cdot 10^{6}$

------ Subtasks ------
Subtask #1 (20 points):
$T ≤ 10$
$N ≤ 10$

Subtask #2 (80 points): original constraints

----- Sample Input 1 ------
4

1

-1 1

1

0 0

2

4 3 1 4

3

5 3 7 10 5 10
----- Sample Output 1 ------
0

1

2

4

见题面

见题面