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

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.

Input Format Count Arrays solution codechef

  • The first line contain s 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 Count Arrays solution codechef

  • 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

Sample Input 1 

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

Leave a Comment

Your email address will not be published.