#include <fstream>
#include <iostream>
using namespace std;

#define m 1999999973

unsigned int n, p, r;
unsigned int p2[32], pmax;

inline void citire()
{
	ifstream fin("lgput.in");
	fin >> n >> p;
	fin.close();
}
inline void scriere()
{
	ofstream fout("lgput.out");
	fout << r << '\n';
	fout.close();
}
inline void exponentiere()
{
	r = 0;
	p2[0] = n;
	for (pmax = 1; (1 << pmax) <= p; pmax++)
		p2[pmax] = p2[pmax - 1] * p2[pmax - 1] % m;
	p2[pmax] = p2[pmax - 1] * p2[pmax - 1] % m;
	for (int i = pmax; i > 0; i--)
	{
		if (p >= (1 << i))
		{
			p -= (1 << i);
			r = (r + p2[i]) % m;
		}
	}
}
int main()
{
	citire();
	exponentiere();
	scriere();
	return 0;
}