# [Solution] Good Permutations Solution Codechef

## [Solution] Good Permutations Solution Codechef

You are given two arrays  and , each of size .

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

• ��=��+��� or ��=��−���, for all (1≤�≤�);
• All elements of  are equal.

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

Note that a permutation of length  consists of all integers from 1 to  exactly once.

### Input Format

• The first line of input will contain a single integer , 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  – the size of arrays.
• The second line of each test case consists of  space-separated integers �1,�2,…,��, the elements of array A.
• The third line of each test case consists of N space-separated integers �1,�2,…,��, the elements of array B.

### Output Format Good Permutations Solution Codechef

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

### Constraints Good Permutations Solution Codechef

• 1≤�≤105
• 1≤�≤105
• −109≤��≤109
• −109≤��≤109
• The sum of  over all test cases won’t exceed 2⋅105.

### Sample 1: Good Permutations Solution Codechef

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
1
2
6
24

### Explanation: Good Permutations Solution Codechef

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

• �1=�1+��1=�1+�3=10−1=9;
• �2=�2−��2=�2−�2=5−(−4)=9;
• �3=�3−��3=�3−�1=2−(−7)=9.

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

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

• �1=�1−��1=�1−�2=6−5=1;
• �2=�2+��2=�2+�1=7+(−6)=1;
• �3=�3−��3=�3−�3=8−7=1.

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