#include <bits/stdc++.h>
#define var long long

using namespace std;

ifstream fin("lgput.in");
ofstream fout("lgput.out");

const var MOD = 1999999973;

var n, p;

int main()
{
    fin >> n >> p;
    var ans = 1, pow = 1;
    for(var i = 0; (1<<i) <= p; ++i){
        if(i ==0)
            pow = n % MOD;
        else
            pow = (pow * pow)%MOD;
        var mask = (1<<i);
        if((p&mask))
            ans = (ans * pow)%MOD;


    }

    fout << ans % MOD;

    return 0;
}