#include <cstdio>

using namespace std;

void rid(int &n, int p, int curr_it) {
	n %= 1999999973;

    if (p < (1<<(curr_it + 1)))
        return;

	int tempn = n;
    n *= n;

	rid(n, p, curr_it + 1);

	if (p & (1<< curr_it))
	{
		n *= tempn;
	}
}




int main() {
	freopen("lgput.in", "r", stdin);
	freopen("lgput.out", "w", stdout);

	int n, p;
	scanf("%d%d", &n, &p);

	rid(n, p, 0);

	printf("%d\n", n);

	return 0;
}