/*
 * =====================================================================================
 *
 *       Filename:  putere.cpp
 *
 *    Description: Dandu-se doua numere naturale N si P, se cere sa se calculeze
 *                 restul impartirii lui NP la 1999999973.
 *
 *        Version:  1.0
 *        Created:  11/06/2012 01:18:19 AM
 *       Revision:  none
 *       Compiler:  gcc
 *
 *         Author:  YOUR NAME (), 
 *   Organization:  
 *
 * =====================================================================================
 */

#include<iostream>
#include<cstdio>

using namespace std;

const int m = 1999999973;

int main()
{
	int n,p;
	long long int x,sol = 1;
	FILE *in,*out;
	in = fopen("lgput.in","r");
	out = fopen("lgput.out","w");
	fscanf(in,"%d %d",&n,&p);
	x = n;
	for(int i = 0 ; (1<<i) <= p ; i++) // luam toti bitii din scrierea binara a lui p la rand
	{
		if( ((1<<i) & p) != 0 )  // verificam daca bitul de pe pozitia i(numarand din dreapta,evident) este 1
			sol = (sol * x) % m;   
		x = (x * x) % m;
	}
	fprintf(out,"%lld",sol);
	fclose(in);
	fclose(out);
	return 0;
}