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

const unsigned long X=1999999973;

int main()
{
	unsigned int P;
	unsigned long long rez=1,N;
	fstream fin("lgput.in",fstream::in);
	fstream fout("lgput.out",fstream::out);
	fin>>N>>P;
	fin.close();
	for(unsigned long i=0; (1<<i) <= P; ++i)
	{
		cout<<(1<<i)<<endl;
		if( (1<<i) & P)
			rez=(rez*N)%X;
		N=(N*N)%X;
	}
	fout<<rez<<endl;
	fout.close();
	return 0;
}