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

using namespace std;


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

unsigned int n,p,nr,i,m;

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

        if((m&n)==m)
        {

            nr=(p*nr)%1999999973;

        }
         p=(p*p)%1999999973;


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