#include<fstream.h>
#include<math.h>
long a;


long put(int x,int n)
{
 if(!n)return 1;
 else
 if(n%2) return (x*(put(x,n-1)%a))%a;
 else return (put(x,(n>>1))%a)*(put(x,(n>>1))%a);
 }

int main()
{

 long n,p;
 ifstream f("lgput.in");
 ofstream g("lgput.out");
 f>>n>>p;
 a=1999999973;
 n%=a;
 p%=(a-1);
 g<<put(n,p);
 return 0;
 }