SPOJ -> POWERUP - Power the Power Up

#include<bits/stdc++.h>
#define MOD 1000000007
using namespace std;
long long fast(long long base , long long exp , long long mod)
{
   long long res = 1;
     while(exp){
       if(exp&1)
        res = (res%mod * base%mod) % mod;
        exp = exp >> 1;
        base = (base%mod * base%mod) % mod;
        }
        return res;

}
int main(){

                   while(true){

                       long long a , b , c;
                        cin >> a >> b >> c;
                        if(a == -1 &&  b == -1 && c == -1)
                             break;
                         if(c == 0)
                          cout << (a%MOD) <<endl;
                          else
                         if(b == 0)
                          cout <<"1" << endl;
                          else
                          if(a%MOD == 0)
                          cout <<"0"<<endl;
                          else {
                        long long result2 = fast( b , c , MOD-1);
                        long long result1 = fast(a , result2 , MOD);
                        cout << result1 << endl;
                      }
                   }
                   return 0;
}