#include <iostream>
#include <fstream>
#define mod 1999999973

using namespace std;

long long int lgput(long long int n, long long int p) {
    if (p == 0) {
        return 1;
    } else {
        long long int res = lgput(n, p / 2);
        if (p % 2 == 1) {
            return (((n * res) % mod) * res) % mod;
        } else {
            return (res * res) % mod;
        }
    }
}

int main() {

    long long int n, p;
    ifstream in("lgput.in");
    ofstream out("lgput.out");
    in >> n >> p;
    out << lgput(n, p);
    return 0;
}