// https://infoarena.ro/problema/lgput
// Dandu-se doua numere naturale N si P, se cere sa se calculeze restul impartirii lui N^P la 1999999973.

#include <iostream>
#include <fstream>
#include <cmath>

using namespace std;

unsigned long long int MOD = 1999999973;

// Functia calculeaza baza^exponent folosind exponentierea rapida
long long ExponentiereRapida(unsigned long long int base, unsigned long long int exponent)
{
	unsigned long long int result = 1;
	while (exponent > 0)
	{
		if (exponent % 2 == 1)
			result = (result * base) % MOD;
		base = (base * base) % MOD;
		exponent /= 2;
	}
	return result;
}

int main()
{
    ifstream fin("lgput.in");
	ofstream fout("lgput.out");

    if (!fin.is_open())
    {
        cerr << "Eroare la deschiderea fisierului de intrare!";
        return 1;
    }
	if (!fout.is_open())
	{
		cerr << "Eroare la deschiderea fisierului de iesire!";
		return 1;
	}


	unsigned long long int N, P;
	fin >> N >> P;
	if (N < 2 || P > pow(2, 32))
	{
		cerr << "Nu se respecta restrictiile: N <= 2 si P <= 2^32";
		return 1;
	}
	
	fout << ExponentiereRapida(N, P) << endl;
	
	fin.close();
	fout.close();

	return 0;
}