[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.

Leave a Comment