# [Solution] Count Arrays solution codechef

Count Arrays solution codechef – Given an array AA of length NN such that 1AiN1≤Ai≤N and Aii,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]:

• BiBAiBi≠BAi
• 1BiM1≤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 NNMM.
• 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

• 1T1051≤T≤105
• 2N1052≤N≤105
• 1M1001≤M≤100
• 1AiN,Aii1≤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].