#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <sstream>
#include <chrono>
#include <thread>
#include <cstdlib>

using namespace std;
ifstream in("lgput.in");
ofstream out("lgput.out");

typedef long long ll;
const ll mod = 1999999973;

ll N,K;

int main() {
    in>>N>>K;

    ll res = 1;
    while (K) {
        if (K&1) {
            res = (res * N) % mod;
        }
        N = (N*N) % mod;
        K >>= 1;
    }

    out<<res<<'\n';
    in.close();out.close();
    return EXIT_SUCCESS;
}