#include <iostream>
#include <fstream>
using namespace std;
 
ofstream fo("lgput.out");
ifstream fi("lgput.in");
 
 
 long long prim=1999999973,b,p,raspuns=1;
int main()
{
 
    fi>>b>>p;
 
    for(int i=1;i<(1<<30);i*=2)
    {
        if(i&p)
        raspuns=raspuns*b%prim;
 
        b=b*b%prim;
    }
 
    fo<<raspuns%prim;
    return 0;
}