#include <fstream>
#include <string>
#include <math.h>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>

#define infile "lgput.in"
#define outfile "lgput.out"

#define n_max
#define INF 1 << 30
#define MOD 1999999973

#define ll long long
#define ull unsigned long long

#define pb push_back
#define mkp make_pair
#define pii pair<int, int>
#define FOR(g) \
    for(vector<int>::iterator it=g.begin(); it!=g.end(); ++it)
#define nxt (*it)

#define min(x,y) x<y ? x : y
#define max(x,y) x>y ? x : y
using namespace std;

ull N, P;


void read(){
    ifstream fin(infile);

    fin >> N >> P;

    fin.close();
}

ull powlog(){
    ull res = 1;
    ull pow = N;

    for(ull bit = 0; (1<<bit) <= P; ++bit){
        if(P & (1<<bit))
           res = (res * pow) % MOD;
        pow  = (pow * pow) % MOD;
    }
    return res;
}

void print(){
    ofstream fout(outfile);

    fout << powlog();

    fout.close();
}


int main(){

    read();

    print();

    return 0;
}