Chemicals

There are N bottles each having a different chemical. For each chemical i, you have determined C[i], which means that mixing chemicals i and C[i] causes an explosion. You have K distinct boxes. In how many ways can you divide the N chemicals into those boxes such that no two chemicals in the same box can cause an explosion together?

The first line of input is the number of test cases T. T test cases follow each containing 2 lines.

The first line of each test case contains 2 integers N and K.

The second line of each test case contains N integers, the ith integer denoting the value C[i]. The chemicals are numbered from 0 to N-1.

For each testcase, output the number of ways modulo 1,000,000,007.

• T ≤ 50
• 2 ≤ N ≤ 100
• 2 ≤ K ≤ 1000
• 0 ≤ C[i] < N
• For all i, i ≠ C[i]

In the first test case, we cannot mix any 2 chemicals. Hence, each of the 3 boxes must contain 1 chemical, which leads to 6 ways in total.

In the third test case, we cannot put the 3 chemicals in the 2 boxes satisfying all the 3 conditions.