#include <iostream>
#include <stdio.h>

using namespace std;


FILE *f=fopen("lgput.in","r");
FILE *g=fopen("lgput.out","w");

unsigned long long  cn,n,p,nr,i,m;

int main()
{
    fscanf(f,"%d%d",&n,&p);
    cn=n;
    nr=1;
    for(i=0;i<32;i++)
    {
        m=1<<i;

        if((m&p)==m)
        {

            nr=(cn*nr)%1999999973;

        }
         cn=(cn*cn)%1999999973;


    }
    fprintf(g,"%d",nr);
    fclose(g);
    return 0;
}