#include <iostream>
#include <fstream>
using namespace std;

typedef long long llong;

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

long long n, p, sol;
const int modulo = 1999999973;

llong Qpow(llong n, llong p);

int main()
{
    fin >> n >> p;

    fout << Qpow(n, p) % modulo << '\n';

    fin.close();
    fout.close();
    return 0;
}

llong Qpow(llong n, llong p)
{
    if ( p < 0 )      return Qpow(1/n, -p);
    if ( p == 0 )     return 1;
    if ( p == 1 )     return n;
    if ( p % 2 == 0 ) return Qpow( n*n, p/2);
    if ( p % 2 == 1 ) return Qpow( n*n, (p-1)/2 );
}