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

int n,p;

int f()
{
	int nr=n;
	while(p!=0)
	{
		cout<<" p : "<<p<<" "<<nr<<endl;
		p-=2;
		//exp/=2;
		nr=(nr*nr)%1999999973;
	}
	return nr;
}


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