#include<stdio.h>
#define MOD 1999999973
int n , p;
long long sol=1 , a;
int main()
{
    freopen("lgput.in" , "r" , stdin);
    freopen("lgput.out" , "w" , stdout);
    scanf("%d %d" , &n , &p);
    sol=1;
    a=n;
    for (int i=0 ; (1 << i) <= p ; ++i)
    {
        if( ((1 << i) & p) > 0)
            sol=(sol * a) % MOD;
        a=(a * a) % MOD;
    }
    printf("%lld\n" , sol);
}