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取模的结果。

一行，由单个空格分隔的三个正整数，分别表示a、n和m。

对于100%的数据：

0\le a,n \le 2^{31} ；

1\le m \le 2^{31} 。

一行，一个整数，表示结果。

当n为0时，a^n=1。