#include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++) #define rep(i,n) repl(i,0,n) #define mp(a,b) make_pair(a,b) #define pb(a) push_back(a) #define all(x) (x).begin(),(x).end() #define dbg(x) cout<<#x"="<0){ if(n&1) res = res*x%m; x=(x*x)%m; n>>=1; } return res; } int main(){ long a,b,c; string s; cin>>s; int idx=s.find('^'); a = stol(s.substr(0, idx)); int i2 =s.find('^', idx+1); b = stol(s.substr(idx+1, i2-idx)); int i3 =s.find('^', i2+1); c = stol(s.substr(i2+1, i3-i2)); // dbg(a); dbg(b); dbg(c); long r1 = mod_pow(mod_pow(a, b, MOD), c, MOD); long r2; if(a%MOD==0){ r2=0; } else{ // use a^(p-1) = 1 (mod p) long pw = mod_pow(b, c, MOD-1); r2 = mod_pow(a, pw, MOD); } cout<