#include<fstream>
#include<cmath>
//#include<ctime>

using namespace std;

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

int main()
{
    const int modul = 1999999973;
    unsigned int number, power, maxPower, log, i;
    cin>>number>>power;

    if(power==0)
      {cout<<"1";return 0;}
//    double start=clock();

    log=log2(power);
    maxPower=(1<<log);

    long long result=number;
    for(i=0;i<log;i++)
        result=result*result;
    int actualPower=(1<<log);

    log--;
    while(log!=-1&&actualPower!=power)
    {
        int tempPower=1<<log;
        if(tempPower+actualPower<=power)
        {
          int aux=number;
          for(i=0;i<log;i++)
             aux=(aux*aux)%modul;
          result=(result*aux)%modul; actualPower+=tempPower;
        }
        log--;
    }
    cout<<result<<'\n';
/*
    double finish=clock();
    double time=(finish-start)/CLOCKS_PER_SEC;
    cout<<time<<'\n';

    start=clock();

    result=number;
    for(i=0;i<power-1;i++)
        result*=number;

    finish=clock();
    time=(finish-start)/CLOCKS_PER_SEC;

    cout<<time<<'\n';
*/
    return 0;
}