#include <iostream>
#include <fstream>

//  n ^ p  = mul for each bit i: n^(2^i), when i = 1
// (a*b*c)%d = a%d * b%d * c%d

using namespace std;

ifstream fin("lgput.in");
ofstream fout("lgput.out");

unsigned int bx = 1999999973;
unsigned int n, p;

int main()
{
    fin >> n >> p;
    long long sol = 1, a = n;
    long long mask = 1;
    do{
        if((mask &p) > 0) sol = (sol*a)%bx; //current bit==1
        a = (a * a)%bx;                     //2^(i+1), bitul urm e mai semnificativ
        mask<<=1;                           //mask for next bit
    }while(mask <= p);
    fout << sol << endl;
    return 0;
}