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.
T <= 50
2 <= N <= 100
2 <= K <= 1000
0 <= C[i] < N
For all i, i != C[i]
For each testcase, output the number of ways modulo 1,000,000,007.
3 3 3 1 2 0 4 3 1 2 0 0 3 2 1 2 0
6 12 0
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.
Migrated from old NTUJ.
Regional Amritapuri 2010
| No. | Testdata Range | Score |
|---|