#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;
    int64 bit = 1;
    int64 pos = 0;
    while (bit <= n) { 
          if (n & bit) ret*=memo[pos], ret%=M;
          bit*=2LL; pos++;
          }

    cout << ret << '\n';

    return 0;
    }