#include <bits/stdc++.h>
#define prim 1999999973

using namespace std;
int n,p,z;


inline int solutie(unsigned long long x, unsigned long long y)
{
    if(y==1) return x%prim;
    if(y==0) return 1;
    if(x==1) return 1;
    if(y%2==0) return solutie((x*x)%prim,y/2)%prim;
    return x%prim*solutie((x*x)%prim,(y-1)/2)%prim;
}



int main()
{
    ifstream fin("lgput.in");
    ofstream fout("lgput.out");
    fin>>n>>p;
    fout<<solutie(n,p);
    fout.close();
    fin.close();
    return 0;
}