#include<fstream>
#include<iostream>
using namespace std;
ifstream f("lgput.in");
ofstream g("lgput.out");
unsigned long long int a,b,c;
int main()
{
    unsigned long long int i,n,p;
    f>>a>>b;
    c=1999999973;
    n=1;
    p=a;
    //b=(a+1)/2*a;
    //c=1000000009;
    while(b!=0)
    {
        if(b&1==1)
            n*=p;
        p*=p;
        p%=c;
        n%=c;
        b>>=1;
    }
    g<<n;
    f.close();
    g.close();
    return 0;
}