[Solution] Count Arrays solution codechef

Count Arrays solution codechef – Given an array AA of length NN such that 1≤Ai≤N1≤Ai≤N and Ai≠i,Ai≠i, ∀i∈[1,N]∀i∈[1,N].

Count the number of arrays BB of length NN such that ∀i∈[1,N]∀i∈[1,N]:

• Bi≠BAiBi≠BAi
• 1≤Bi≤M1≤Bi≤M

Since the answer may be large, print it modulo 109+7109+7.

Count Arrays solution codechef

• The first line contains a single integer TT − the number of test cases. The description of TT test cases follows.
• Each test case contains 22 lines of input:
  • The first line of each test case contains two space separated integers NN, MM.
  • The second line of each test case contains NN space separated integers A1,A2,…,ANA1,A2,…,AN.

Output Format

For each test case, output a single integer on a newline – answer modulo 109+7109+7.

Constraints

• 1≤T≤1051≤T≤105
• 2≤N≤1052≤N≤105
• 1≤M≤1001≤M≤100
• 1≤Ai≤N,Ai≠i1≤Ai≤N,Ai≠i
• Sum of NN over all test cases does not exceed 106106

Count Arrays solution codechef

 

2
2 3
2 1
3 2
2 1 1

Sample Output 1 

6
2

Explanation Count Arrays solution codechef

Test Case 11: There are 66 possible arrays – [1,2],[2,1],[1,3],[3,1],[2,3],[3,2][1,2],[2,1],[1,3],[3,1],[2,3],[3,2].

Test Case 22: There are 22 possible arrays – [1,2,2],[2,1,1][1,2,2],[2,1,1].