#include <fstream>
#include <cmath>
#define x 1999999973

using namespace std;

ifstream fin("lgput.in");
ofstream fout("lgput.out");

long long n, p, last;
long long V[35], i, sol;

int main()
{
    fin>>n>>p;
    last=log(p)/log(2);
    V[0]=n;
    for (i=1; i<=last; i++)
    {
        V[i]=V[i-1]*V[i-1]%x;
    }
    for (i=0; i<=last; i++)
    {
        if ((1<<i)&p)
            sol+=V[i]%x;
    }
    fout<<sol;
    return 0;
}