#include <iostream>

using namespace std;
typedef long long int64;
int64 n, p;
int64 M = 1999999973LL;
int64 memo[34];
int main() {
    freopen("lgput.in", "r", stdin);
    freopen("lgput.out", "w", stdout);
    cin >> n >> p;
    memo[0] = n;
    int64 i;
    for (i = 1; i < 33; ++i) memo[i] = (memo[i-1] * memo[i-1])%M; 
    int64 ret = 1;
    for (i = 32; i >= 1; --i) if (p & (1 << (i))) ret*=memo[i], ret%=M;
    cout << ret << '\n';

    return 0;
    }