实验室新研制出了一种十分厉害的$Virus$（病毒）。这个病毒被植入了特殊的微型芯片，使其可以被人为的控制。

最重要的一个优点是，人类可以自行设定病毒的分裂能力$K$，假如现在有$x$个病毒，下一个分裂周期将会有 $K \times x$个一模一样的病毒。

你作为该实验室的数据分析员，需要统计出在分裂到第$N$个周期前，一共有多少个病毒单体进行了分裂。一开始时总是只有一个病毒，这个局面算作第一个周期。由于答案可能很大，专家们只需要你告诉他们对给定的$P$取模后的答案。

输入格式

一行三个整数，依次是$K, N, P$。

输出格式

一行一个整数，你的答案（对P取模） 。

样例

样例输入1

5 3 7

样例输出1

6

• 样例一解释：第一个周期有 $1$ 个病毒，产生了一次分裂。第二个周期有 $1 \times 5=5$ 个病毒， 这五个病毒都会分裂。 所以第三个周期前一共进行了$1+5$等于 $6$ 次分裂。 答案即为6 mod 7 = 6。

样例输入2

2 6 23

样例输出2

8

数据范围与提示

• $1 \leq N \leq 10^{18}$
• $1 \leq K , P \leq 2^{31}$