#include <iostream>
#include <fstream>
#define MOD 1999999973
using namespace std;
ifstream in("lgput.in");
ofstream out("lgput.out");

long long lgput(long long n, long long p)
{
    long long nd, s=1, a = n, i;
    for(i=0; (i<<1)<=p;i++)
    {
        if((1<<i) & p)
            s=(s*a) % MOD;
        a = (a*a) % MOD;
    }
    return s;
}
int main()
{
    long long n,p;
    in>>n>>p;
    out<<lgput(n,p);
    return 0;
}