#include <iostream>
#include <fstream>

using namespace std;

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

int main()
{
    unsigned int n, p;
    long long result, scale;
    fin >>n >>p;
    scale = n;
    result = 1;
    for (unsigned int i = 0; (1<<i) < p ; ++i)
    {
         if ( ((1<<i) & p) > 0)
            result = (result * scale) % 1999999973;
        scale = (scale * scale) % 1999999973;
    }
    fout <<result <<'\n';
    return 0;
}