#include <cstdio>
#define ll long long
#define md 1999999973

using namespace std;

ll N,P;

int main(){

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

    ll a = N,i,S = 1;
    for(i = 0;(1 << i) <= P;++i){

      if((1 << i) & P)S = (S * S) % md;
      a = (a * a) %md;

    }

    printf("%lld\n",S);

    return 0;
}