#include <iostream>
#include <cstdio>
using namespace std;

int nrf=1;

void f(int nr,int putere)
{
	for(int i=1;i<=putere/2;i++)
		nrf=(((nrf%1999999973)*nr)%1999999973*nr)%1999999973;
	printf("%d",nrf);
}


int main()
{
	freopen("lgput.in","r", stdin);
	freopen("lgput.out","w", stdout);
	int n,p;
	scanf("%d %d",&n,&p);
	if(p%2==0) f(n,p);
	else 
	{
		nrf*=n;
		p--;
		f(n,p);
	}
	return 0;
}