#include <cstdio>
using namespace std;

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

    p2=1;
    for(j=i;j>=1;--j)
    {
        if(b[j]==1)
            p2=p2*p2*a;
        else
            p2=p2*p2;
    }
    printf("%lld", p2%1999999973);

    return 0;
}