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


long fct(int n,int p)
{
 long r,s=n,pp=1;
 if(n==1) return 1;
 while(s<a)
 {
  s*=n;
  pp++;
  }
 if(p<pp)return pow(n,p);
 else
 {
 r=pow(n,(p%pp));
 n=s%a;
 p/=pp;
 return (r*fct(n,p))%a;
 }
 }

int main()
{

 long n,p;
 ifstream f("lgput.in");
 ofstream g("lgput.out");
 f>>n>>p;
 g<<fct(n,p);
 return 0; 
 }