时间限制：1秒　　内存限制：256M

---

【问题描述】

　　A学校的实验室新研制出了一种十分厉害的病毒。由于这种病毒太难以人工制造了，所以专家们在一开始只做出了一个这样的病毒。

　　这个病毒被植入了特殊的微型芯片，使其可以具有一些可编程的特殊性能。最重要的一个性能就是，专家们可以自行设定病毒的分裂能力 \(K\)，假如现在有 \(x\) 个病毒，下一个分裂周期将会有 \(K^x\) 个一模一样的病毒。你作为该实验室的数据分析员，需要统计出在分裂到第 \(N\) 个周期前，一共有多少个病毒单体进行了分裂。一开始时总是只有一个病毒，这个局面算作第一个周期。由于答案可能很大，专家们只需要你告诉他们对给定的 \(P\) 取模后的答案。

【输入格式】

　　一行三个整数，依次是 \(K, N, P\)。

【输出格式】

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

【输入输出样例1】

　Input

5 3 7

　Output

6

【输入输出样例2】

　Input

2 6 23

　Output

8

【数据说明】

　　对于 \(100\%\) 的数据 \(1 < N < 10^18\)，\(1 < K , P < 2^31\)。

【来源】

　　Mr.he