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$.