#include <bits/stdc++.h>
#define mod 1999999973

unsigned int n, p;
long long a, sol = 1;

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

	scanf("%d %d", &n, &p);
	a = n;
	for (int i = 0; (1<<i) <= p; ++i) { //luam toti bitii lui p la rand
		if ((1<<i) & p) //daca bitul i din p este 1 atunci adaugam n^(2^i) la solutie
			sol = (sol * a) % mod;

        a = (a * a) % mod; //inmultim a cu a ca sa obtinem n^(2^(i+1))
	}

	printf("%lld\n", sol); // Afisam solutia
	return 0;
}