#include<iostream>
#include<fstream>
#include<cmath>
using namespace std;
ifstream fin("lgput.in");
ofstream fout("lgput.out");
 
bool A[33];
long long n, p, s = 1, nr = 1;
 

void binar()
{
    long long p1 = p;
    long long x = powl(2, 32);
    for(int i = 32; i >= 0; --i)
    {
        if(p1 >= x)
        {
            A[i] = 1;
            p1 -= x;
        }
        x /= 2;
    }
}
 
int main()
{
    fin>>n>>p;
    binar();
    nr = n;
    for(int i = 0; i <= 32; ++i)
    {
        if(A[i] == 1)
        {
            s *= nr;
            s %= 1999999973;
        }
        nr *= nr;
        nr %= 1999999973;
    }
    fout<<s;
 
}