#include <iostream>
#include <fstream>

#define Q 1999999973

using namespace std;

int main()
{
    unsigned long long n, p;

    // open files
    freopen("lgput.in", "r", stdin);
    freopen("lgput.out", "w", stdout);

    // read input
    cin >> n >> p;

    // solve
	unsigned long long sol = 1;

    for (int i = 0; (1 << i) <= p; i++)
    {
        if (((1 << i) & p)) sol = (sol * n) % Q;
		n = (n * n) % Q;
    }

    // write output
    cout << sol;

    return 0;
}