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.

3 2 4
2 10 1000

1
24

 //2017-08-04

 #include <cstdio>

 #include <cstring>

 #include <iostream>

 #include <algorithm>

 #define ll long long 

 using namespace std;

 const int N = ;

 char b[N];

 ll a, c;

 ll quick_pow(ll a, ll n, ll MOD){

     ll ans = ;

     while(n){

         if(n&)ans = ans*a%MOD;

         a = a*a%MOD;

         n>>=;

     }

     return ans;

 }

 ll phi(ll n){

     ll ans = n;

     for(ll i = ; i*i <= n; i++){

         if(n%i==){

             ans -= ans/i;

             while(n%i==)

                 n /= i;

         }

     }

     if(n > )ans = ans - ans/n;

     return ans;

 }

 int main()

 {

     while(scanf("%lld%s%lld", &a, b, &c)!=EOF){

         ll len = strlen(b);

         ll MOD = phi(c), num = ;

         for(ll i = ; i < len; i++)

             num = (num* + b[i]-'')%MOD;

         num += MOD;

         printf("%lld\n", quick_pow(a, num, c));

     }

     return ;

 }