#include<fstream>
using namespace std;
long long n,m,p,sol,aux,i;
int main()
{
    ifstream fin("lgput.in");
    ofstream fout("lgput.out");
    fin>>n>>m;
    p=1;
    sol=m;
    while(sol>1)
    {
        p=p*n%1999999973;
        i=1;
        aux=n;
    while(i*2<=sol)
    {
        p=p*aux%1999999973;
        aux=aux*aux%1999999973;
        i=i*2;
    }
    sol-=i;
    }
    if(sol==1)
        p=p*n%1999999973;
    fout<<p;
}