#include <fstream>
#include <iostream>

using namespace std;
ifstream fin("lgput.in");
ofstream fout("lgput.out");
long long int n,p,a;
void lgput();
int main()
{
        fin >> n >> p;
        a = 1;
        lgput();
        fout << n;
    return 0;
}

void lgput()
{
    int n1 = n, a1 = a;
    if (2*a <= p)
    {
        n = (n * n)% 1999999973;
        a = a * 2;
        lgput();
        if (a + a1 == p) {
            n = (n * n1) % 1999999973;
            a = a + a1;
        }
    }
}