#include<iostream>
#include<fstream>
using namespace std;
ifstream fin("lgput.in");
ofstream fout("lgput.out");
long long n,p,e=1,x=1,m;
bool v[32];
int main()
{
    fin>>n>>p;
    while(p>0)
    {
        m++;
        if(p%2==1) v[m]=1;
        p/=2;
    }
    x=n;
    for(int i=1;i<=m;i++)
    {
        if(v[i]==1)
        {
            e*=x;
            e%=1999999973;
        }
        x*=x;
        x%=1999999973;    }
    fout<<e%1999999973;
}