나눗셈의 춤

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

요약

N명의 남녀가 두 원에서 K번 회전하며 춤을 출 때, 모든 커플의 나이 합 나머지가 M으로 같아지는 방법의 수를 10^9+7로 나눈 나머지로 구합니다.

난이도: 어려움10점 중 8점
유형: 수학, 정수론, 조합론
정답자: 아직 제출이 없습니다

문제

Nlogônia 나라 사람들은 나눗셈의 신을 기리기 위해 특별한 춤을 춘다. 춤은 $N$ 명의 남자와 $N$ 명의 여자가 두 개의 원에 서서 추며, 남자는 안쪽 원, 여자는 바깥쪽 원에 선다. 처음에 각 여자는 남자 한 명과 마주 본다.

춤은 $K$ 번의 동작으로 이루어지며, 남자부터 시작해 남자와 여자가 번갈아 움직인다. $i$ 번째 동작에서는 한 원의 사람들이 시계 방향으로 $P_i$ 칸 회전하고, 다른 원의 사람들은 제자리에 있는다. 그러면 각 사람은 $P_i$ 칸 떨어진 사람과 새 파트너가 된다. 동작은 다음 두 조건을 모두 만족할 때 유효하다. 동작을 시작할 때와 끝낼 때 각 사람의 파트너가 달라야 하고, 서로 마주 보는 두 사람의 쌍이 서로 다른 두 시점에 나타나면 안 된다.

춤은 반드시 커플의 나이 합을 신성한 수 $M$ 으로 나눈 나머지가 모두 같은 상태로 끝나야 한다. 즉 어떤 커플의 나이 합을 $M$ 으로 나눈 나머지가 $R$ 이면, 춤이 끝났을 때 모든 커플의 나이 합을 $M$ 으로 나눈 나머지도 $R$ 이어야 한다.

$N$ , $M$ , $K$ 와 모든 춤꾼의 나이가 주어졌을 때, 춤을 출 수 있는 방법의 수를 구하라. 나이는 초 단위로 측정되므로 값이 매우 클 수 있다.

입력

첫째 줄에 세 정수 $N$ ( $3 \le N \le 10^6$ ), $M$ ( $1 \le M \le 10^9$ ), $K$ ( $1 \le K \le 10^9$ )가 주어진다. 각각 한 원에 서는 사람 수, 신성한 수, 동작의 수이다.

둘째 줄에는 여자들의 나이 $A_i$ ( $1 \le A_i \le 10^9$ )가 공백으로 구분되어 주어진다. 셋째 줄에는 남자들의 나이 $B_i$ 가 주어진다. 처음에 $i$ 번째 남자는 $i$ 번째 여자와 나란히 서 있다. 각 배열의 첫 번째 원소는 마지막 원소의 오른쪽에 이어져 있다고 본다.

출력

서로 다른 춤의 수를 $10^9 + 7$ 로 나눈 나머지를 정수 하나로 출력한다.

예제4

예제 1
입력
```
4 10 1
3 4 1 7
13 27 36 9
```
예상 출력
```
1
```
예제 2
입력
```
5 10 2
3 4 1 7 6
4 7 1 2 5
```
예상 출력
```
3
```
예제 3
입력
```
5 10 2
3 4 1 7 6
5 4 7 1 2
```
예상 출력
```
4
```

예제 4

입력

6 21 3
10 58 23 31 37 2
45 17 9 24 38 30

예상 출력