题目描述：

求$a^b \% p$ 的值。提示：若 $b$ 为偶数，$a^b=(a^2)^{\frac{b}{2}}$；若 $b$ 为奇数，$a^p=a*(a^2)^{\frac{b-1}{2}}$，该题可以采用分治法求解。

输入格式：

三个不超过 10000 的正整数$a，b，p$。

输出格式：

输出一行一个字符串 a^b mod p=s，其中 $a,b,p$分别为题目给定的值， $s$ 为运算结果。

2 10 9

2^10 mod 9=7

提示

对于100%的数据，$a、b \le 2^{31}$,$2 \le p \le 2^{31}$