시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
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.