Given A,B,C, You should quickly calculate the result of A^B mod C. (1<=A,B,C<2^63).
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.
1000000008 10000000000000 1000000007 2 10 1000 3 2 4
1 24 1