固定一个整数 $k \ge 2$，并定义函数 $f: \mathbb{N} \to \mathbb{N}$：

$$f(n) = \begin{cases} n/k, & \text{如果 } k \mid n \\ n - 1, & \text{其他情况} \end{cases}$$

如果我们取某个整数 $n \ge 1$ 并对它应用函数 $f$ 若干次（可能为 0 次），最终我们将得到 1。例如，当 $k = 3$ 时，$f(f(f(f(f(16))))) = f(f(f(f(15)))) = f(f(f(5))) = f(f(4)) = f(3) = 1$。

你的任务是计算有多少个这样的 $n$，使得经过恰好 $m$ 次迭代后我们得到 1。答案可能非常大，因此你需要输出它对 $mod$ 取模的结果。

输入格式

第一行包含三个由空格分隔的整数：$k, m, mod$ ($2 \le k \le 10^4, 0 \le m \le 10^{18}, 2 \le mod < 300$)。保证 $mod$ 是质数。

输出格式

输出一个整数：问题的答案对 $mod$ 取模的结果。

样例

样例输入 1

2 4 31

样例输出 1

5

样例输入 2

3 13 59

样例输出 2

36

说明

$\mathbb{N}$ 是正整数集。