시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 256 MB 1 1 1 100.000%

문제

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

예제 입력 1

2 4 31

예제 출력 1

5

예제 입력 2

3 13 59

예제 출력 2

36

힌트

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