/* フェルマーの小定理 Fermat's little theorem a^(p-1) == 1 (mod p) pは素数 a,pは互いに素 N^M == (N % p)^(M % (p-1)) p: 素数 */ #include #include #include #include #include #include #define FORR(i,b,e) for(int i=(b);i<(int)(e);++i) #define FOR(i,e) FORR(i,0,e) #define ALL(c) begin(c), end(c) #define sortuniq(v) sort(v.begin(), v.end()), v.erase(unique(v.begin(),v.end()),v.end()) #define dump(var) cerr << #var ": " << var << "\n" #define dumpc(con) for(auto& e: con) cerr << e << " "; cerr<<"\n" typedef long long ll; typedef unsigned long long ull; const double EPS = 1e-6; const int d4[] = {0, -1, 0, 1, 0}; using namespace std; const ll MOD = 129402307; ll getnum(string &s, ll p) { ll res = 0; for (char &c: s) { res *= 10; res += c - '0'; res %= p; } return res; } ll powmod(ll n, ll m, ll p) { ll res = 1; while (m > 0) { if (m & 1) res = (res*n) % p; m /= 2; n = n * n % p; } return res; } int main() { cin.tie(0); ios::sync_with_stdio(false); ll N, M; string S; cin >> S; N = getnum(S, MOD); S.clear(); cin >> S; M = getnum(S, MOD-1); if (M == 0) { cout << 1 << endl; } else if (N == 0) { cout << 0 << endl; } else { cout << powmod(N, M, MOD) << endl; } return 0; }