#include <iostream>
#include <cstdio>
using namespace std;

#define Max 1999999973

unsigned long long int n,p;

unsigned long long int pwr(unsigned long long int x,unsigned long long int y)
{
    if(y==1)
        return x;
    else if(y%2==0)
                return pwr(x*x,y/2);
    else return x*pwr(x*x,y/2);
}

int main()
{
    freopen("lgput.in","r",stdin);
    freopen("lgput.out","w",stdout);
    scanf("%llu%llu",&n,&p);
    printf("%llu",pwr(n,p)%Max);

    return 0;
}