#include #include #include #include #include #include #include // string, to_string, stoi #include // vector #include // min, max, swap, sort, reverse, lower_bound, upper_bound #include // pair, make_pair #include // tuple, make_tuple #include // int64_t, int*_t #include // printf #include // map #include // queue, priority_queue #include // set #include // stack #include // deque #include // unordered_map #include // unordered_set #include // bitset #include // isupper, islower, isdigit, toupper, tolower using namespace std; using ll = long long; #define rep(i, n) for (long long i = 0; i < (long long)(n); i++) ll Max(ll(a), ll(b), ll(c)) { return max(max(a, b), c); } ll Min(ll(a), ll(b), ll(c)) { return min(min(a, b), c); } struct UnionFind { vector par; // par[i]:iの親の番号 (例) par[3] = 2 : 3の親が2 UnionFind(int N) : par(N) { //最初は全てが根であるとして初期化 for (int i = 0; i < N; i++) par[i] = i; } int root(int x) { // データxが属する木の根を再帰で得る:root(x) = {xの木の根} if (par[x] == x) return x; return par[x] = root(par[x]); } void unite(int x, int y) { // xとyの木を併合 int rx = root(x); //xの根をrx int ry = root(y); //yの根をry if (rx == ry) return; //xとyの根が同じ(=同じ木にある)時はそのまま par[rx] = ry; //xとyの根が同じでない(=同じ木にない)時:xの根rxをyの根ryにつける } bool same(int x, int y) { // 2つのデータx, yが属する木が同じならtrueを返す int rx = root(x); int ry = root(y); return rx == ry; } }; ll Q[4000002]; ll modPow(long long a, long long n, long long p) { if (n == 0) return 1; // 0乗にも対応する場合 if (n == 1) return a % p; if (n % 2 == 1) return (a * modPow(a, n - 1, p)) % p; long long t = modPow(a, n / 2, p); return (t * t) % p; } ll Xor(ll a, ll b) { ll A = a, B = b; ll C = 0; ll k = 1; while (A > 0 || B > 0) { if (A % 2 != B % 2) { C += k; } k *= 2; A /= 2; B /= 2; } return C; } ll mod = 1e9 + 7; ll stll(string S,ll mod) { ll n = 0; ll k = 1; rep(i, S.size()) { n += (k * int(S[S.size() - i - 1]-'0')); k *= 10; k %= mod; n %= mod; } return n; } vector stbi(string S) { vector k(1e7); return k; } int main() { ll N, M,K=129402307; string S,T; cin >> S >> T; N = stll(S, K); M = stll(T, K - 1); if (M == 0) { cout << 1 << endl; return 0; } if (N == 0) { cout << 0 << endl; return 0; } cout << modPow(N,M,K) << endl; }