#include <iostream>
#include <fstream>

#define MOD 1999999973

using namespace std;

int main() {
    freopen("lgput.in", "r", stdin);
    freopen("lgput.out", "w", stdout);

    long long n, p;
    int result;
    int times_two = 0;

    cin >> n >> p;

    result = n;

    while (p > 1) {
        if (p % 2) {
            times_two++;
            p--;
        } else {
            result = (result * result) % MOD;
            p /= 2;
        }
    }
    while (times_two) {
        result = (result * n) % MOD;
        times_two--;
    }

    cout << result;
}