#include <iostream>
#include <fstream>

using namespace std;

ifstream f("lgput.in");
ofstream g("lgput.out");

const int MOD = 1999999973;

int main()
{
    unsigned int i, n, p;
    long long a, sol = 1;
    f >> n >> p;
    a = n;
    for(i = 0; (1 << i) <= p; ++i) /// Luam toti bitii lui p la rand
    {
        if(((1 << i)&p) > 0) /// Daca bitul i din p este 1 atunci adaugam n^(2^i) la solutie
            sol = (sol * a) % MOD;
        a = (a * a) % MOD; /// Inmultim a cu a ca sa obtinem n^(2^(i+1))
    }
    g << sol;
    f.close();
    g.close();
    return 0;
}