#include #include #include #include #include #include #include #include #include #include using namespace std; const long long modc = 129402307; long long mod_exp(long long b, long long e, long long m){ if (e > 0 && b == 0) return 0; long long ans = 1; b %= m; while (e > 0){ if ((e & 1LL)) ans = (ans * b) % m; e = e >> 1LL; b = (b*b) % m; } return ans; } long long div(string S, long long P){ long long N = S.size(), res = 0; for (int i=0; i> S >> T; long long N = div(S, modc), M = div(T, modc-1); if (N == 0 && T != "0"){ cout << 0 << endl; return 0; } cout << mod_exp(N, M, modc) << endl; return 0; }