깃발 퍼포먼스

시간 제한2초메모리 제한1024 MB

요약

초기 깃발 배치가 주어졌을 때 K번의 두 사람 교환으로 모든 깃발을 제 주인에게 되돌리는 순서의 수를 10억 7을 법으로 구합니다.

난이도: 보통10점 중 7점
유형: 조합론, 동적 계획법, 수학
정답자: 아직 제출이 없습니다

문제

당신은 정렬 체조 팀을 맡고 있다. 이 새로운 종목은 $N$ 명으로 이루어진 팀이 겨루는 경기다. 각 팀원은 서로 다른 색의 의상( $1$ 부터 $N$ 까지의 번호)을 입고, 색이 있는 깃발을 하나씩 든다. 깃발의 색은 모두 다르며, 역시 $1$ 부터 $N$ 까지 번호가 붙어 있다. 공연은 정확히 $K$ 번의 단계로 이루어진다. 각 단계마다 두 팀원이 깃발을 서로 맞바꾼다. 깃발의 초기 배치는 자유롭게 정할 수 있다. 단, 공연이 끝났을 때 모든 참가자가 자신의 의상 색과 같은 번호의 깃발을 들고 있어야 한다.

팀의 주장으로서 공연을 최대한 예측하기 어렵게 만들고 싶다. 주어진 $T$ 개의 초기 배치마다, 팀이 이 과제를 수행하는 방법의 수를 구하라. 답이 매우 클 수 있으므로 소수 $1000000007$ 로 나눈 나머지를 출력한다.

입력

첫 줄에 정수 $N$ , $K$ , $T$ 가 공백으로 구분되어 주어진다. 이어서 $T$ 개의 줄이 주어진다. $k$ 번째 줄에는 서로 다른 정수 $N$ 개 $c_{k,1}, c_{k,2}, \dots, c_{k,N}$ 이 공백으로 구분되어 있다. 여기서 $c_{k,i}$ 는 의상 색이 $i$ 인 팀원이 처음에 들고 있는 깃발의 색 번호다.

출력

$T$ 개의 줄을 출력한다. $k$ 번째 줄에는 $k$ 번째 초기 배치에서 시작해 위 조건을 만족하는 교환 순서의 수를 $1000000007$ 로 나눈 나머지를 출력한다.

제한

$2 \le N \le 30$

$1 \le K \le 50$

$1 \le T \le 10000$

예제3

예제 1
입력
```
4 2 1
4 1 2 3
```
예상 출력
```
0
```
예제 2
입력
```
4 3 1
4 1 2 3
```
예상 출력
```
16
```

예제 3

입력

6 15 10
5 6 1 2 4 3
2 4 1 6 5 3
4 1 3 6 5 2
1 3 2 4 5 6
4 5 6 1 2 3
1 2 5 3 6 4
6 4 2 3 1 5
3 6 4 1 2 5
4 5 1 2 6 3
6 1 4 3 2 5

예상 출력