#include <bits/stdc++.h>

using namespace std;
#define mod 1999999973
ifstream in("lgput.in");
ofstream out("lgput.out");

int main()
{
    int base ,put,ans,i;
    in>>base>>put;
    ans=1;
    for(i=0;(1<<i)<=put;++i){
        if(((1<<i)&put)>0)
            ans=(1LL*ans*base)%mod;
        base=(1LL*base*base)%mod;
    }
    out<<ans;
    return 0;
}