#include <fstream>
#define imp 1999999973
using namespace std;
int main()
{
	ifstream ii("lgput.in");
	ofstream oo("lgput.out");
	unsigned long long n, p, i, rest = 0, put = 1;  ii >> n >> p;
	unsigned long long r[32];  r[0] = n % imp;
	if (p % 2) rest = r[0];
	for (i = 1; i < 32; i++)
	{
		r[i] = (r[i-1]*r[i-1]) % imp;  put *= 2;
		if (p & put)
			rest = (rest + r[i]) % imp;
	}
	oo << rest;
}