Chemicals
시간 제한1초메모리 제한1024 MB
각 화학물질 i에 폭발 상대 C[i]가 주어질 때, 폭발하는 두 물질이 같은 상자에 들어가지 않도록 N개의 물질을 K개의 상자에 나누는 경우의 수를 구한다.
문제
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.