#include <iostream>
#include <cstdio>
using namespace std;
long long n,p,put,i,sol=1;
int main()
{
    freopen("lgput.in","r",stdin);
    freopen("lgput.out","w",stdout);
    scanf("%li %li",&n,&p);
    long long m=1999999973;
    for (i=0;(1<<i)<=p;++i)
    {
         if ( ((1<<i) & p) > 0)
            sol= (sol * n) % m;

            n=(n * n) % m;
    }
    cout<<sol;
}