#include <iostream>

using namespace std;

int main()
{
    long long n, p, r, R, i = 0, a;
    cin>>n>>p;
    R = 1999999973;
    ///(1<<i) = 2 ^i;
    a = n;
    r = 1;
    while ((1<<i) <= p)
    {
        if (((1<<i)&p) != 0)
            r = (r * a) % R;
        a = (a * a) % R;
        i++;
    }
    cout<<r;
    /*while (p > 0)
    {
       n = n * n;
       p = p - 1;
    }
    n = n % r;
    cout<<n;
    */

    /*while (n / 2 > 0)
    {
        s = s * 10 + n % 2;
    }
    cout<<s;
    */
    return 0;
}