#include <cstdio>
using namespace std;

unsigned long long p2;
int x,a,i,p,j,b[1001];
int main ()
{
    freopen("lgput.in", "r", stdin);
    freopen("lgput.out", "w", stdout);
    scanf("%d%d", &p, &a);
    i=0;
    while(p>0)
    {
        ++i;
        b[i]=p%2;
        p=p/2;
    }
    x=1999999973;
    p2=1;
    for(j=i;j>=1;--j)
    {
        if(b[j]==1)
            p2=((p2%x)*(p2%x)*(a%x))%x;
        else
            p2=((p2%x)*(p2%x))%x;
    }
    printf("%lld", p2%1999999973);

    return 0;
}