#include <fstream>
using namespace std ;
ifstream f("lgput.in");
ofstream g("lgput.out");

long n,p;

void citire ()
{
  f>>n>>p;
  f.close ();
}

int main ()
{
  const long mod=1999999973;
  long i;
  long long sol=1,a;
  citire ();
  a=n;
  for (i=0; (1<<i)<=p; i++)   // Luam toti biti lui p la rand 
  {
	if (((1<<i)&p)>0)        // Daca bitul i din p este 1 atunci adaugam n^(2^i) la solutie  
	  sol=(sol*a)%mod;       //(am scris >0 pentru ca nu da 0 sau 1 ci 0 sau un numar (numar=a&b)
	a=(a*a)%mod;              // Inmultim a cu a ca sa obtinem n^(2^(i+1))  (2,2^2,2^4,2^8.....)
  }
  g<<sol;
  g.close ();
  return 0;
}
//In varianta iterativa practic descompunem pe p in puteri ale lui 2 si inmultim : n^(p1+p2...)=n^p1*n^p2...
  
/*Varianta recusiva
power(x,n)= { 1, daca n=0;
              x*power (x,n-1), daca n este impar
              (power(x,n/2))^2, daca n este par (x^(n/2)*x^(n/2)=x^n)
            }
sau mai eficient power (x,n)= { 1, daca n=0,
                                x*(power(x,[n/2]))^2
                              }
*/