#include <iostream>
#include <fstream>
#define mod 1999999973
using namespace std;
long long  n,p;
int main()
{
    fstream f,g;
    f.open("lgput.in",ios::in);
    g.open("lgput.out",ios::out);
    f>>n>>p;
    long long i,sol =     1;
    for( i = 0 ; (1<<i) <= p; i++)
    {
        if ( ((1<<i) & p) ){
            sol = (sol * n) % mod;
        }
        n = (n* n) % mod;
    }
    g<<sol;
}