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.

 import java.util.Scanner;

 import java.math.BigInteger;

 public class Main {

     public static void main(String[] args) {

         Scanner scan = new Scanner(System.in);

         while(scan.hasNext()){

             BigInteger a = scan.nextBigInteger();

             BigInteger b = scan.nextBigInteger();

             BigInteger c = scan.nextBigInteger();

             System.out.println(a.modPow(b,c));//大整数乘方和取模

         }

     }

 }