#include <bits/stdc++.h>
using namespace std;

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

#define REST 1999999973

int main()
{
    long long n, p;
    fin >> n >> p;

    long long put = n, rez = 1;

    for(int i = 0; (1 << i) <= p; ++i)
    {
        if((p & (1 << i)) > 0)
        {
            rez = (rez * put) % REST;
        }

        put = (put * put) % REST;
    }
    fout << rez;
}