24703번 - Lucky Tickets 다국어

문제

The government plans a transport reform which will change ticket numbers. The new ticket numbers will consist of $q$ digits in $n$-ary number system, where $q$ is a prime number. Leading zeros are allowed.

A ticket is considered lucky if the product of all its digits added to the sum of all its digits, taken modulo $n,ドル equals $s$. Additionally, every lucky ticket has a degree of luckiness: the degree of luckiness of the ticket with digits $a_1 a_2 \ldots a_q$ equals $$(a_1 + 1) (a_2 + 2) \ldots (a_q + q) + 2^0 a_1 + 2^1 a_2 + \ldots + 2^{q-1} a_q\text{.}$$

For reform report, it is needed to calculate the sum of luckiness of all lucky tickets modulo $q$.

입력

The first line contains three integers $n,ドル $s$ and $q$ (2ドル \le n \le 10^6,ドル 0ドル \le s < n,ドル 2ドル \le q \le 10^6,ドル $q$ is prime).

출력

Print the sum of luckiness of all lucky tickets modulo $q$.

제한

힌트