#include<cstdio>
using namespace std;
int main()
{
    freopen("lgput.in","r",stdin);
    freopen("lgput.out","w",stdout);
    long long n,p,cn,ans=1;
    scanf( "%lld%lld" , &n,&p );
    cn = n;
    for ( int bit = 0 ; (1<<bit) <= p ; ++bit ){
        if ( p & (1<<bit) )
            ans = ans * n % 1999999973;
        n = n * n % 1999999973;
    }
    printf ("%lld",ans);
    return 0;
}