Saloni has two sets A and B, both of having N distinct elements. Sets A and B have exactly N - K same elements (K <= N). Therefore, exactly K elements differ in sets A and B. Now you insert both the sets into two lists C and D.
Now Saloni loves the scenario when C[i] != D[i] for any value of i from 1 to N.
You are allowed to permute both the arrays C and D. Find the number of ways in which Saloni loves the permutation of the two arrays. (The total number of ways to permute both arrays = N! * N! )
As the answer can be huge, find it modulo 109 + 7.
The first line of input contains an integer Q, denoting the number of queries.
The next Q lines contain two integers N and K.
1 <= Q <= 100000
1 <= N <= 10000
0 <= K <= N
Query 1: C = [a, b, c] and D = [a, b, c]. One valid combination is [b, a, c] and [a, c, b].
Query 2: C = [a, b, c] and D = [a, b, d]. One valid combinations are [a, b, c] and [b, a, d].
Query 3: C = [a, b, c] and D = [d, e, f]. All permutations of both the arrays are valid. So, 3! * 3! = 36.
if anyone can please provide a code or solution, preferably in C++ or Java