#include <cstdio>

using namespace std;

void rid(long long &n, long long p, long long 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;
		n %= 1999999973;
	}
}




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

	long long n, p;
	scanf("%lld%lld", &n, &p);

	rid(n, p, 0);

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

	return 0;
}