#include<stdio.h>

#define rest 1999999973

long long res, n, p;

int main()
{
    freopen ("lgput.in", "r", stdin);
    freopen ("lgput.out", "w", stdout);
    scanf("%lld %lld", &n, &p);
    res=1;
    while(n){
        if( n%2==0 ){
            res=(res*p)%rest;
            n--;
        }
            else{
                p=(p*p)%rest;
                n=n/2;
            }
    }

    printf("%lld\n", res);
    return 0;
}