100523 - 快速幂
如果用朴素方法求解a^n时，将会计算n-1次乘法，如果b非常大，那么这将消耗非常多的时间。如果把幂指数n拆分为二进制形式，将会有所改观。以n=13为例，朴素算法需要计算12次乘法，而拆分n之后：
a^{n}=a^{11}={a^{2}}^{3}＊{a^{2}}^{2}＊{a^{2}}^{0}
此时，只需运行7次乘法。求a^n的结果对m取模的结果。
Input
一行，由单个空格分隔的三个正整数，分别表示a、n和m。
对于100%的数据：
0\le a,n \le 2^{31} ；
1\le m \le 2^{31} 。
Output
一行，一个整数，表示结果。
Examples
Input
2 32 123456
Output
56512
Hint
当n为0时，a^n=1。