#include <iostream>
#include <fstream>
using namespace std;
ifstream f("lgput.in");
ofstream g("lgput.out");
int i,aux,m=0;
bool c[10000];
long long p,n,a[100];
int main()
{
f>>n>>p;
int s=1;
a[0]=n;
for (i=1;i<=32;i++)
{
    a[i]=a[i-1]*a[i-1];
    a[i]%=1999999973;

}

while (p)
{
    m++;
    aux=p%2;
    c[m]=aux;
    p/=2;

}

long long prod=1;
for (i=1;i<=m;i++)
{
if (c[i]==1) prod*=a[i-1];

prod%=1999999973;
}
g<<prod;



    return 0;
}