#include <fstream>
#define md 1999999973
using namespace std;

ifstream fi ("lgput.in");
ofstream fo ("lgput.out");

long long n, p, a = 1, s, cn;

int main ()
{
    fi >> n >> p;
    cn = n;
    while (a*2 < p || a*2 == p)
    {
        n = (n*n)%md;
        a*=2;
    }
    if (p - a > 0)
    {
        p-=a;
        s+=n;
        cn = n;
        a = 1;
    }
    else
    {
        fo << n;
        return 0;
    }

    return 0;
}