#include <iostream>
#include <algorithm>
#include <fstream>
#include <string>

using namespace std;

#define FILE_IN "lgput.in"
#define FILE_OUT "lgput.out"

typedef unsigned int uint;

#define MODULO 1999999973ULL

uint N, P;

uint putere(uint N, uint P)
{
    uint rezultat = 1ULL;

    for (int i=31-__builtin_clz(P); i>=0; i--)
    {
        rezultat = (rezultat * rezultat) % MODULO;
        if (P & (1ULL << i)) rezultat = (N * rezultat) % MODULO;
    }

    return rezultat;
}

int main()
{
    ifstream fisIn(FILE_IN);
    ofstream fisOut(FILE_OUT);

    fisIn >> N >> P;

    fisOut << putere(N,P);
}