#include <stdio.h>
#include <stdlib.h>
#define MOD 1999999973

int main()
{
    long long a,rez;
    int n,i,p;
    FILE *f=fopen("lgput.in","r");
    FILE *g=fopen("lgput.out","w");

    fscanf(f,"%d%d",&n,&p);

    a=n;
    rez=1;
    for (i=0;(1<<i)<=p;i++)
    {
        if (((1<<i)&p)!=0)
            rez=(rez*a)%MOD;
        a=(a*a)%MOD;
    }

    fprintf(g,"%d\n",(int)rez);
    fclose(f);
    fclose(g);
    return 0;
}