19499번 - K-transform 다국어

문제

Let us fix an integer $k \ge 2$ and define a function $f$: $\mathbb{N} \rightarrow \mathbb{N}$:

$f(n)= \begin{cases} & n / k \text{, if } k \mid n \\ & n - 1 \text{, otherwise} \end{cases}$

If we take some integer $n \ge 1$ and will apply function $f$ some (possibly 0ドル$) times then we will end up with 1ドル$. For example, if $k=3$ then $f(f(f(f(f(16)))))=f(f(f(f(15))))=f(f(f(5)))=f(f(4))=f(3)=1$.

Your task is to calculate the amount of such $n$ that we will end up with 1ドル$ after exactly $m$ iterations. The answer may be very large, so you have to output it modulo $\mathit{mod}$.

입력

The first line contains three integers separated by spaces: $k,ドル $m,ドル $\mathit{mod}$ (2ドル \le k \le 10^{4},ドル 0ドル \le m \le 10^{18},ドル 2ドル \le \mathit{mod} < 300$). It is guaranteed that $\mathit{mod}$ is prime.

출력

Print one integer: the answer to the problem modulo $\mathit{mod}$.

제한

힌트

$\mathbb{N}$ is the set of positive integers.