#include <iostream>
#include <fstream>
#include <cstring>
#include <cstdio>

using namespace std;
int v[35];


int main()
{
    freopen ("lgput.in","r",stdin);
    freopen ("lgput.out","w",stdout);
    int i,c=0;
    long long r,n,p,prod=1;
    scanf("%lld %lld",&n,&p);
    while(p)
    {
        v[c++]=p%2;
        p/=2;
    }
    r=n;
    for(i=0;i<c;i++)
    {
        if(v[i])
            prod=prod*r%1999999973;
        r=r*r%1999999973;
    }
    printf("%lld\n",prod);











    return 0;
}