#include <bits/stdc++.h>
#define MOD 1999999973

using namespace std;
ifstream fin("lgput.in");
ofstream fout("lgput.out");
typedef long long ll;

ll n, p, sol = 1LL;
ll pown[35];

int main()
{

    fin >> n >> p;

    pown[0] = n;
    for(int i = 1; i < 35; ++i){
        pown[i] = (pown[i - 1] * pown[i - 1]) % MOD;
    }

    while(p){
        ll lg = ll(log2(p));
        p -= (1LL << lg);

        sol = (sol * pown[lg]) % MOD;
    }

    fout << sol;

    return 0;
}