Count Arrays solution|Codesheff starter 25 for div 3

Given an array A$A$ of length N$N$ such that 1≤Ai≤N$1\le A_i\le N$ and Ai≠i,$A_i\ne i,$ ∀i∈[1,N]$\mathrm{\forall }i\in [1,N]$.

Count the number of arrays B$B$ of length N$N$ such that ∀i∈[1,N]$\mathrm{\forall }i\in [1,N]$:

• Bi≠BAi$B_i\ne B_{A_i}$
• 1≤Bi≤M$1\le B_i\le M$

Since the answer may be large, print it modulo 109+7${10}^9+7$.

Input Format

• The first line contains a single integer T$T$ − the number of test cases. The description of T$T$ test cases follows.
• Each test case contains 2$2$ lines of input:
  • The first line of each test case contains two space separated integers N$N$, M$M$.
  • The second line of each test case contains N$N$ space separated integers A1,A2,…,AN$A_1,A_2,\dots ,A_N$.

Output Format

For each test case, output a single integer on a newline - answer modulo 109+7${10}^9+7$.

Constraints

• 1≤T≤105$1\le T\le {10}^5$
• 2≤N≤105$2\le N\le {10}^5$
• 1≤M≤100$1\le M\le 100$
• 1≤Ai≤N,Ai≠i$1\le A_i\le N,A_i\ne i$
• Sum of N$N$ over all test cases does not exceed 106${10}^6$

Sample Input 1 

2
2 3
2 1
3 2
2 1 1

Sample Output 1 

6
2

Explanation

Test Case 1$1$: There are 6$6$ 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 2$2$: There are 2$2$ possible arrays - [1,2,2],[2,1,1]$[1,2,2],[2,1,1]$.

Solution:

click here for solution