#include <iostream>

using namespace std;

#define mod 1999999973

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

    int n, p;
    int64_t a, sol;
    cin >> n >> p;

    a = n;
    sol = 1;
    for (int i = 0; (1 << i) <= p; ++i) {
        if ( ((1 << i) & p) > 0 ) {
            sol = (sol * a) % mod;
        }
        a = (a * a) % mod;
    }
    printf("%lld", sol);

    return 0;
}