K의 배수 Extreme

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

요약

K가 N의 약수일 때, 1부터 N까지 각 수가 적힌 공이 M개씩 있습니다. 이 중 하나 이상을 골라 합이 K의 배수가 되는 경우의 수를 10^9+7로 나눈 나머지로 구합니다.

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

문제

준혁이는 1부터 $N$ 까지의 수가 적힌 공을 각각 $M$ 개씩 가지고 있다. 같은 숫자가 적힌 $M$ 개의 공은 모두 색이 다르다. 준혁이는 $N$ 의 약수 중 하나를 $K$ 로 정하고, 가지고 있는 $N\times M$ 개의 공 중 한 개 이상을 골라 적힌 수의 합이 $K$ 의 배수가 되도록 하는 경우의 수를 구하려고 한다.

뽑은 공 중 하나라도 색이 다르거나 적힌 수가 다르면 서로 다른 경우로 센다.

입력

첫 번째 줄에 정수 $N$ , $M$ , $K$ 가 공백으로 구분되어 주어진다. ( $1\le N, M, K\le 10^6$ )

출력

공에 적힌 수들의 합이 $K$ 의 배수가 되도록 한 개 이상의 공을 뽑는 경우의 수를 $10^9+7$ 로 나눈 나머지를 출력한다.

$10^9+7$ 은 소수이다.

예제5

예제 1
입력
```
4 1 1
```
예상 출력
```
15
```
예제 2
입력
```
4 1 2
```
예상 출력
```
7
```
예제 3
입력
```
3 2 3
```
예상 출력
```
23
```
예제 4
입력
```
4 5 4
```
예상 출력
```
262143
```
예제 5
입력
```
33 1 3
```
예상 출력
```
863312881
```