#define _CRT_SECURE_NO_DEPRECATE

#include <cstdio>
#include <iostream>
#include <vector>
using namespace std;

#define MOD 1999999973
#define ll long long 

ll N, P, X;
vector<bool> bits;

int main(){
	ll i, j;

	//freopen("test.in", "r", stdin);
	freopen("lgput.in", "r", stdin);
	//freopen("test.out", "w", stdout);
	freopen("lgput.out", "w", stdout);

	cin >> N >> P;
	while (P){
		bits.push_back(P % 2);
		P /= 2;
	}

	X = 1;
	for (i = bits.size() - 1; i >= 0; i--){
		X *= X, X %= MOD;
		if (bits[i]){
			X *= N, X %= MOD;
		}
	}

	cout << X;

	return 0;
}