#include<bits/stdc++.h>
using namespace std;
ifstream in ("lgput.in");
ofstream out ("lgput.out");
int main()
{
    unsigned long long int a,b,y,sum=1;
    in>>a>>b;
    for (int i=0;i<32;i++){
        y=pow(2,i);
        if ( (b&y)+0 == y){
            sum=sum*pow(a,y);
        }
        sum=sum%1999999973;
    }
    out<<sum;
    return 0;
}