#include <fstream>
#include <stack>
using namespace std;
#define MOD 1999999973

ifstream is ("lgput.in");
ofstream os ("lgput.out");

int n, p;
long long x;

stack <bool> s;

int main()
{
    is >> n >> p;
    while (p)
    {
        s.push(p % 2);
        p /= 2;
    }
    x = 1;
    while (!s.empty())
    {
        x *= x;
        if (s.top() == 1)
            x *= n;
        s.pop();
        x %= MOD;
    }
    os << x;
    is.close();
    os.close();
    return 0;
}