#include <bits/stdc++.h>
#define MOD 1999999973
using namespace std;

ifstream fin("lgput.in");
ofstream fout("lgput.out");

int main()
{
    long long b,p,nr,i=1,sol=1;
    fin>>b>>p;
    nr=b;
    while(p!=0)
    {
       if((i&p)==i)
           sol*=nr,p-=i;
       i+=i;
       nr*=nr;
       nr%=MOD;
       sol%=MOD;
    }
    fout<<sol;
    return 0;
}