TLE的乘幂

题目描述:

TLE讨厌长长的题面。因此他出了一句话题面：给出a，b，c，求a^b(a的b次方)在mod c意义下的值。

输入格式:

第一行3个整数a,b,c。

输出格式:

输出共一行，一个整数，为题意所求的答案。

样例输入:

6 2 10

样例输出:

6

提示:

对于40%的数据，a<=2000,b<=3000,c<=4000;

对于70%的数据，b<=300000;

对于100%的数据，1<=a<=1e⁹,1<=b<=2e⁹,1<=c<=2e⁹。

例子：计算 6¹⁰⁰  % 10

6^100=(6^50)*(6^50)%10

6^50=(6^25)*(6^25)%10

6^25=(6^12)*(6^12)%10*6%10

6^12=(6^6)*(6^6)%10

6^6=(6^3)*(6^3)%10

6^3=(6^1)*(6^1)%10*6%10

注意：每次乘了以后对c取余，不然会超出范围。

时间限制: 1000ms
空间限制: 128MB

---

来源: by cyb