#include <fstream>
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] = 1;
	p2[1] = n;
	for (pmax = 2; (1 << pmax) <= p; pmax++)
		p2[pmax] = p2[pmax - 1] * p2[pmax - 1] % m;
	pmax++;
	p2[pmax] = p2[pmax - 1] * p2[pmax - 1] % m;
	for (int i = pmax; i >= 0; i--)
	{
		if (p >= (1 << i))
		{
			p -= 1 << i;
			r += p2[i] % m;
		}
	}
}
int main()
{
	citire();
	exponentiere();
	scriere();
	return 0;
}