#include <bits/stdc++.h>
using namespace std;
ifstream fin ("lgput.in"); ofstream fout ("lgput.out");
const int n_max = 1001; // Numarul maxim de cifre al numerelor
const int modulo = 1999999973; // numarul la care trebie sa impartim rezultatul

int main ()
{
	unsigned int i, n, p;
	long long a, sol = 1;
	fin >> n >> p;
	a = n;
	for (i = 0; (1<<i) <= p; i++) // am luat toti bitii lui p pe rand
	{
		if (((1<<i) & p) > 0) // daca bitul i din p este 1 atunci adaugam n^(2^i)
			sol = (sol * a) % modulo;
		a = (a * a) % modulo; // inmultim a cu a ca sa obtinem n^(2^(i+1))
	}
	fout<< sol ;
	return 0;
}