#include <bits/stdc++.h>

using namespace std;
long long n, p, x, r, i;
int a[10000];
int main()
{
    ifstream fin("lgput.in");
    ofstream fout("lgput.out");
    fin >> n >> p;
    r=1;
    for(i=1; p; i++)
    {
        a[i]=p%2;
        p/=2;
    }
    while(i)
    {
        r=(r*r)%1999999973;
        if(a[i]==1)
        {
            r=(r*n)%1999999973;
        }
        i--;
    }
    fout <<r;
    return 0;
}