K의 배수 Extreme

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

요약

1부터 N까지의 수가 적힌 공을 각각 M개씩 가진 상황에서, K가 N의 약수일 때 뽑은 공의 합이 K의 배수가 되는 비어 있지 않은 부분집합의 수를 1e9+7로 나눈 나머지를 구한다.

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

문제

준혁이는 $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$ 은 소수이다.

예제6

예제 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
```
예제 6
입력
```
780885 280188 780885
```
예상 출력
```
457247866
```