#include <iostream>
#include <cstdio>
#define M 1999999973
using namespace std;

int N,P;
long long int A;
long long int Sol;

int main()
{
    freopen("lgput.in","r",stdin);
    freopen("lgput.out","w",stdout);
    scanf("%d %d",&N,&P);
    Sol=1;
    A=N;
    for(int i=0;(1<<i)<=P;++i)
    {
        if(((1<<i) & P)>0)
            Sol=(Sol*A)%M;
        A=(A*A)%M;
    }
    printf("%lld",Sol);
    return 0;
}