AMR10J - Mixing Chemicals

no tags 

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?
 
INPUT
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.
 
OUTPUT
For each testcase, output the number of ways modulo 1,000,000,007.
 
CONSTRAINTS
T <= 50
2 <= N <= 100
2 <= K <= 1000
0 <= C[i] < N
For all i, i != C[i]
 
SAMPLE INPUT
3
3 3
1 2 0
4 3
1 2 0 0
3 2
1 2 0
 
SAMPLE OUTPUT
6
12
0
 
EXPLANATION
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.


hide comments
Daniel Macintyre: 2011-04-20 17:57:27

Your answer would be 0 because you have garbage input.

You can't have the second line be 1 2 0 3.
Remember you are listing C[i] in that line - you're line in longer form says this:
C[0] = 1
C[1] = 2
C[2] = 0
C[3] = 3

i.e. your fourth chemical causes an explosion when interacting with itself - it will explode even if put in a box alone!

rizki achmad: 2011-01-04 07:09:38

what is the answer of:
4 3
1 2 0 3
??

Re:
For all i, i != C[i]

Last edit: 2011-04-01 06:54:33

Added by:Varun Jalan
Date:2010-12-13
Time limit:0.308s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:own problem, ICPC Asia regionals, Amritapuri 2010