#include <fstream>
#define Mod %1999999973

using namespace std;

ifstream cin("lgput.in");
ofstream cout("lgput.out");

typedef unsigned __int64 unt;

unt n,p;

unt PowLog(unt b,unt p)
{
    if(p==0)
        return 1;

    if(p==1)
        return b;

    if(p%2)
        return (b*PowLog(b*b Mod,(p-1)/2)) Mod;
    else
        return PowLog(b*b Mod,p/2) Mod;

}

int main()
{
    cin>>n>>p;
    cout<<PowLog(n,p);
    return 0;
}