행운의 티켓

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

요약

n진수 q자리 번호 중 각 자릿수의 합과 곱을 더한 값을 n으로 나눈 나머지가 s인 번호들의 행운도 합을 q로 나눈 나머지를 구합니다.

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

문제

정부가 티켓 번호를 바꾸는 교통 개혁을 추진한다. 새 티켓 번호는 $n$ 진법으로 표현한 $q$ 자리 수로 이루어지며, $q$ 는 소수다. 앞자리 0은 허용된다. 티켓의 모든 자릿수의 곱과 모든 자릿수의 합을 더한 값을 $n$ 으로 나눈 나머지가 $s$ 와 같으면 그 티켓은 행운의 티켓이다. 모든 행운의 티켓에는 행운도가 정해져 있다. 자릿수가 $a_1 a_2 \ldots a_q$ 인 티켓의 행운도는 $(a_1 + 1)(a_2 + 2) \ldots (a_q + q) + 2^0 a_1 + 2^1 a_2 + \ldots + 2^{q-1} a_q$ 이다. 개혁 보고서를 위해 모든 행운의 티켓 행운도의 합을 $q$ 로 나눈 나머지를 구한다.

입력

첫째 줄에 세 정수 $n$ , $s$ , $q$ 가 주어진다 ( $2 \le n \le 10^6$ , $0 \le s < n$ , $2 \le q \le 10^6$ , $q$ 는 소수다).

출력

모든 행운의 티켓 행운도의 합을 $q$ 로 나눈 나머지를 출력한다.

예제3

예제 1
입력
```
2 0 2
```
예상 출력
```
0
```
예제 2
입력
```
10 9 2
```
예상 출력
```
1
```
예제 3
입력
```
3 2 3
```
예상 출력
```
2
```