#include <fstream>
long long a[10000];
using namespace std;

int main()
{
	ifstream f("lgput.in");
	ofstream g("lgput.out");
    long long n, p, x, i=1, j;
    f >> n >> p;
    x=1;
    while(p!=0)
    {
        a[i]=p%2;
        i++;
        p=p/2;
    }
    for(j=i-1;j>=1; j--)
        if (a[j]==0) x=x*x;
        else x=x*x*n;
    g << x% 1999999973;

}