Problem

You are given two arrays �A and �B, each of size �N.

Table of Contents

Let �P denote a permutation length �N. The permutation �P is said to be good, if you can make an array �C where:

��=��+��Ci=Ai+BPi or ��=��−��Ci=Ai−BPi, for all (1≤�≤�)(1≤i≤N);
All elements of �C are equal.

Out of the �!N! possible permutations, find the count of good permutations.
Since the count can be huge, output it modulo 109+7109+7.

Note that a permutation of length �N consists of all integers from 11 to �N exactly once.

Input Format

The first line of input will contain a single integer �T, denoting the number of test cases.
Each test case consists of multiple lines of input.
- The first line of each test case consists of a single integer �N – the size of arrays.
- The second line of each test case consists of �N space-separated integers �1,�2,…,��A1,A2,…,AN, the elements of array A.
- The third line of each test case consists of N space-separated integers �1,�2,…,��B1,B2,…,BN, the elements of array B.

Output Format

For each test case, output on a new line, the count of good permutations, modulo 109+7109+7.

Constraints

1≤�≤1051≤T≤105
1≤�≤1051≤N≤105
−109≤��≤109−109≤Ai≤109
−109≤��≤109−109≤Bi≤109
The sum of �N over all test cases won’t exceed 2⋅1052⋅105.

Sample 1:

Input

Output

4
3
10 5 2
-7 -4 -1
3
6 7 8
-6 5 7
6
2 6 5 5 5 4
7 -5 4 -4 -4 -3
4
2 2 2 2
3 3 -3 -3

Explanation:

Test case 11: The only good permutation is [3,2,1][3,2,1]. We construct �C as following:

�1=�1+��1=�1+�3=10−1=9C1=A1+BP1=A1+B3=10−1=9;
�2=�2−��2=�2−�2=5−(−4)=9C2=A2−BP2=A2−B2=5−(−4)=9;
�3=�3−��3=�3−�1=2−(−7)=9C3=A3−BP3=A3−B1=2−(−7)=9.

Here all elements of array �C are equal. It can be shown that for all other permutations, it is impossible to create such an array �C. Thus, the count of good permutations is 11.

Test case 22: The good permutations are [2,1,3],[3,2,1][2,1,3],[3,2,1]. We construct �C as following using [2,1,3][2,1,3]:

�1=�1−��1=�1−�2=6−5=1C1=A1−BP1=A1−B2=6−5=1;
�2=�2+��2=�2+�1=7+(−6)=1C2=A2+BP2=A2+B1=7+(−6)=1;
�3=�3−��3=�3−�3=8−7=1C3=A3−BP3=A3−B3=8−7=1.

Here all elements of array �C are equal. It can be shown that for [3,2,1][3,2,1], it is possible to create such an array �C. Thus, the count of good permutations is 22.

More Info