[Solution] Good Permutations Solution Codechef

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

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

$C_{i} = A_{i} + B_{P i}$ or $C_{i} = A_{i} - B_{P i}$ , for all $(1 \leq i \leq 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 $1 0^{9} + 7$ .

Note that a permutation of length $N$ consists of all integers from $1$ 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 $A_{1}, A_{2}, \dots, A_{N}$ , the elements of array A.
- The third line of each test case consists of N space-separated integers $B_{1}, B_{2}, \dots, B_{N}$ , 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 $1 0^{9} + 7$ .

Constraints Good Permutations Solution Codechef

$1 \leq T \leq 1 0^{5}$
$1 \leq N \leq 1 0^{5}$
$- 1 0^{9} \leq A_{i} \leq 1 0^{9}$
$- 1 0^{9} \leq B_{i} \leq 1 0^{9}$
The sum of $N$ over all test cases won’t exceed $2 \cdot 1 0^{5}$ .

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

Explanation: Good Permutations Solution Codechef

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

$C_{1} = A_{1} + B_{P 1} = A_{1} + B_{3} = 10 - 1 = 9$ ;
$C_{2} = A_{2} - B_{P 2} = A_{2} - B_{2} = 5 - (- 4) = 9$ ;
$C_{3} = A_{3} - B_{P 3} = A_{3} - B_{1} = 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 $1$ .

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

$C_{1} = A_{1} - B_{P 1} = A_{1} - B_{2} = 6 - 5 = 1$ ;
$C_{2} = A_{2} + B_{P 2} = A_{2} + B_{1} = 7 + (- 6) = 1$ ;
$C_{3} = A_{3} - B_{P 3} = A_{3} - B_{3} = 8 - 7 = 1$ .

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