#include<stdio.h>
#include<stdlib.h>
#define Modulo 1999999973
#define InFile "lgput.in"
#define OutFile  "lgput.out"
long long n,p,y,z;
int main()
{
    freopen(InFile,"rt",stdin);
    freopen(OutFile,"wt",stdout);
    scanf("%lld%lld",&n,&p);
    if(p==0||n<=1) {printf("1"); exit(0);}
    y=1; z=n;
    do
    {
        if((p&1))  y=(y*z)%Modulo ;
        z=(z*z)%Modulo;
        p=p>>1;
    }while(p);
    printf("%lld",y);
    return 0;
}