화학 약품

N개의 병에 각각 서로 다른 화학 물질이 들어 있다. 각 화학 물질 $i$에 대해 $C[i]$가 정해져 있는데, 이는 화학 물질 $i$와 $C[i]$를 섞으면 폭발이 일어난다는 뜻이다. 서로 다른 K개의 상자가 있다. 같은 상자 안에서 폭발을 일으키는 두 화학 물질이 함께 들어가지 않도록 N개의 화학 물질을 이 상자들에 나누어 담는 방법은 몇 가지인가?

첫 줄에 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어지며, 각 테스트 케이스는 두 줄로 이루어진다.

각 테스트 케이스의 첫 줄에는 정수 N과 K가 주어진다.

각 테스트 케이스의 둘째 줄에는 N개의 정수가 주어진다. i번째 정수는 $C[i]$이다. 화학 물질은 0부터 N-1까지 번호가 매겨져 있다.

각 테스트 케이스에 대해 방법의 수를 1,000,000,007로 나눈 나머지를 출력한다.

• $T \le 50$
• $2 \le N \le 100$
• $2 \le K \le 1000$
• $0 \le C[i] < N$
• 모든 $i$에 대해 $i \ne C[i]$

첫 번째 테스트 케이스에서는 화학 물질 두 개를 섞을 수 없다. 따라서 세 상자에 각각 화학 물질이 하나씩 들어가야 하며, 총 6가지 방법이 있다.

세 번째 테스트 케이스에서는 세 조건을 모두 만족하면서 세 화학 물질을 두 상자에 넣을 수 없다.