#include<fstream>
#include<iostream>
#include<algorithm>
#define MDL 1999999973
using namespace std;

ifstream f("lgput.in");
ofstream g("lgput.out");

char v[2001],v2[2001];
int pw[2001];
unsigned long long p,pn;

void read();
void Fmod();
void powr(unsigned long long &,int*);
void div(int A[], int B);
int par(int A[]);

int main()
{
	read();
	Fmod();
	powr(p,pw);
	g<<p;
	f.close();
	g.close();
	return 0;
}

void read()
{
	char *q;
	int lg,i;
	f.getline(v,2000);
	q=strtok(v," ");
	strcpy(v2,q);
	q=strtok(NULL," ");
	strcpy(v,q);
	//cout<<v<<' '<<v2;
	lg=strlen(v);
	for (i=1;i<=lg;++i)
		pw[i]=v[i-1]-'0';
	pw[0]=lg;
	reverse(pw+1,pw+1+pw[0]);
}

void Fmod()
{
	int i=0,lg;
	char c;
	lg=strlen(v2);
	while (i<lg)
	{
		while (p<10&i<lg)
		{
			c=v2[0];
			p=p*10+(c-'0');
			++i;
		}
		p%=MDL;
	}
	pn=p;
}

void div(int A[], int B)
{
      int i, t = 0;
      for (i = A[0]; i > 0; i--, t %= B)
              A[i] = (t = t * 10 + A[i]) / B;
      for (; A[0] > 1 && !A[A[0]]; A[0]--);
}

int par(int A[])
{
	if (A[1]%2==0&&A[0]) return 1;
	else if (A[1]%2) return 2;
	else if (!A[0]) return 3;
}

void powr(unsigned long long &p,int A[])
{
	if (par(A)==1)
	{
		p*=p;
		p%=MDL;
		div(A,2);
		powr(p,A);
	}
	else if (par(A)==2)
	{
		if (A[0]==1&&A[1]==1)
			{
				//A[0]=A[1]=0;
				//p*=pn;
				//p%=MDL;
				return ;
		}
		else 
		{
			A[1]--;
			p*=pn;
			p%=MDL;
			powr(p,A);
		}
	}
	else return ;
}