#include <iostream>
#include <fstream>
using namespace std;

typedef long long int64;
const int64 MOD = 1999999973;
ifstream fin("lgput.in");
ofstream fout("lgput.out");

int main() {
    int N, P;
    fin >> N >> P;
    int64 rez = 1;
    int64 p = 1, lg_p = N;
    while (p <= P) {
        if (p & P) rez = (rez * lg_p) % MOD;
        lg_p = (lg_p * lg_p) % MOD;
        p *= 2;
    }
    fout << rez;
}