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