Given A,B,C, You should quickly calculate the result of A^B mod C. (1<=A,C<=1000000000,1<=B<=10^1000000).

There are multiply testcases. Each testcase, there is one line contains three integers A, B and C, separated by a single space.

For each testcase, output an integer, denotes the result of A^B mod C.

欧拉函数 欧拉定理