#include<stdio.h>
#include <string.h>

using namespace std;

long long x1,k;
/*
long long exp(long long x,long long n)
{
    if(n<0) return exp(1/x,-n);
    if(n==0) return 1;
    if(n==1) return x;
    if(n%2==0) return exp(x*x,n/2);
    else return x*exp(x*x,(n-1)/2);
}
*/
int main()
{
    freopen("lgput.in","r",stdin);
    scanf("%llu %llu",&x1,&k);

    freopen("lgput.out","w",stdout);
    long long res=1;
    for (int i = 0; (1<<i) <= k; ++ i)
    {
        if ( ((1<<i) & k) > 0)
            res= (res * x1) % 1999999973;

            x1=(x1 * x1) % 1999999973;
    }


    printf("%llu",res);
    return 0;
}