#include <stdio.h>
#include <stdint.h>
#include<stdlib.h>

#define mod 1999999973

FILE *file;

int main()
{
	uint32_t n, p;
	long long power, sol = 1;

	file = fopen("lgput.in", "r");
	fscanf(file, "%u ", &n);
	fscanf(file, "%u ", &p);
	fclose(file);

	power = n;
	for (uint32_t i = 0; (1 << i) <= p; ++i)
	{
		if ((1 << i) & p) 
			sol = (sol * power) % mod;

		power = (power * power) % mod; 
	}

	file = fopen("lgput.out", "w");
	fprintf(file, "%lld\n", sol);
	fclose(file);

	return 0;
}