#include<fstream>
#include<iostream>
#define MOD 9901

using namespace std;

ifstream f("sumdiv.in");
ofstream g("sumdiv.out");

int a, b, aa, aux;
long long rez=1;

void Citeste()
{
	f>>aa>>b;
	aux=aa;
}

long long putere(int b)
{
	long long z;
	if (b==0) return 1;
	if (b==1) return a;
	if (b%2==0)
	{
		z=putere(b/2);
		return (z*z)%MOD;
	}
	else 
	{
		z=putere(b/2);
		return ((z*z*a)%MOD);
	}
}

long long suma(int b)
{
	long long z, p;
	if (b==0) return 1;
	if (b%2==1) 
	{
		p=putere((b+1)/2);
		z=suma(b/2);
		return ((z*(p+1))%MOD);
	}
	else 
	{
		p=putere(b);
		z=suma(b-1);
		return ((z+p)%MOD);
	}
}

void Solve()
{
	int d=2, p=0, i;
	long long t;
	if (aa%d==0)
	{
		a=d;
		while (aa%d==0) ++p, aa/=2;
		cout<<d<<" "<<rez<<"\n";
		rez=suma(p*b);
	}
	d=3;
	while (d*d<=aux && aa>1)
	{
		if (aa%d==0) 
		{
			a=d; p=0;
			while (aa%d==0) ++p,aa/=d;
			t=suma(p*b);
			cout<<d<<" "<<rez<<"\n";
			rez=(rez*t)%MOD;
		}
		d+=2;
	}
	if (aa>1)
	{
		//if (aa!=9901) a=aa%MOD; 
		a=aa;
		t=suma(b);
		cout<<a<<" "<<rez<<"\n";
		rez=(rez*t)%MOD;
	}
}

void Afiseaza()
{
	g<<rez<<"\n";
}

int main()
{
	Citeste();
	
	Solve();
	
	Afiseaza();
	
	f.close();
	g.close();
	return 0;
}