#include <iostream>
#include <string>
#include <fstream>
#include <stdio.h>

using namespace std;
typedef long long ll;

const int MOD = 1999999973;

int main()
{
    int N, P;
    ifstream f ("lgput.in");
    ofstream g ("lgput.out");
    
    f >> N >> P;
    ll a = N, sol = 1;

    for (int i = 0; (1ll << i) <= P; ++i) {
        if ((1ll << i) & P)
            sol = (sol * a) % MOD;

        a = (a*a) % MOD;
    }
    g << sol << endl;
    return 0;
}