Migrated from Lutece 2749 For D. E. Knuth

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

当我们回过头去看我们曾经学过的运算时，我们会发现一些有趣的事情：

• 首先我们有加法，加法是好的，我们有 $1+1=2$。
• 然后我们有乘法，乘法也是好的，乘法被定义为一个数本身多次累加，例如 $a\times b$ 可以被理解为 $b$ 个 $a$ 相加。
• 之后我们有幂，幂也是好的，幂被定义为一个数本身多次累乘，例如 $a^b$ 被定义为 $b$ 个 $a$ 相乘。

这是我们所熟悉的一些简单运算，所以我们有一个很好的新运算。

我们定义下一级运算为 $a\uparrow\uparrow b$，你需要理解并计算出 $(a\uparrow\uparrow b) \bmod p$。

Input

第一行三个整数 $a, b, p\ (1\le a,b, p\le 10^9)$。

Output

输出一行一个整数，表示你计算出的答案。

Samples

2 3 1000000007

16

Note

这道题里的运算符号是真实存在的。

Resources

2022 UESTC ICPC Training for Math and Geometry