#include <iostream>
#include <cstdio>
#define MOD 1999999973

using namespace std;

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

    long long n, p, sol = 1;

    scanf("%lld %lld", &n, &p);

    for(int i = 0; (1 << i) <= p; ++i) {
        if(((1 << i) & p) != 0) {
            sol = (sol * n) % MOD;
        }
        n = (n * n) % MOD;
    }

    printf("%lld", sol % MOD);
    return 0;
}