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

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


int main()
{
    const int modulo = 1999999973;
    unsigned int i, N, P, v[1005];
    long long r = 1;
    fin >> N >> P;
    
    int k = 1;
    
    while( P > 0 ){
        v[k++] = P % 2;
        P /= 2;
    }
    
    for( i = k - 1 ; i >= 1 ; --i ){
        
        r = (r * r) % modulo;
        if(  v[i] > 0 ) r = (r * N) % modulo;
    }
    
    fout << r;
    
    return 0;
}