#include <iostream>
#include <fstream>
#define mod 1999999973
using namespace std;

long long n, p;

void read()
{
    ifstream f("lgput.in");
    f >> n >> p;
    f.close();
}

void exp()
{
    ofstream g("lgput.out");
    long long a = n;
    int sol = 1;
    for(int i=0; (1<<i) <= p; ++i)
    {
        if(((1<<i) & p) > 0) sol = (sol * a)%mod;
        a = (a * a) % mod;
    }
    g << sol << '\n';
    g.close();
}

int main()
{
    read();
    exp();
    return 0;
}