#ifdef LOCAL
#include <bits/stdc++.h>
using namespace std;
ifstream fin("file.in");
ofstream fout("file.out");
#else
#include <bits/stdc++.h>
using namespace std;
ifstream fin("lgput.in");
ofstream fout("lgput.out");
//#define fin cin
//#define fout cout
#endif

#define int long long

int n,q,p;
int a,big=1999999973;
vector<pair<int,int>>v;


signed main()
{
    fin>>n>>p;
    a=n;
    q=1;
    v.push_back({a,q});
    while(q<=p/2)
    {
        a*=a;
        a%=big;
        q*=2;
        v.push_back({a,q});
        //cout<<a<<" "<<q<<"\n";
    }
    a=1;
    //cout<<"\n"<<a<<"\n";
    while(p)
    {
        if(v.back().second<=p)
        {
            p-=v.back().second;
            a*=v.back().first;
            a%=big;
        }
        //cout<<a<<" ";
        v.pop_back();
    }
    fout<<a;

    return 0;
}