#include "stdio.h"
#include "string.h"

int prime[3000],N;
void table()
{
	int i,j,k;
	bool hash[8005];
    memset(hash,0,sizeof(hash));
    N = 0;
    for(i = 2;i < 86;i++)
    	if(hash[i] == 0)
    		for(j = i*i;j <= 8000;j = j + i)
    			hash[j] = 1;
    
    for( i = 2;i <= 8000 ;i++ )
    	if(hash[i] == 0)
    		prime[N++] = i;   
} 

int binary(int a,int b,int mod)
{
	int anw = 1,temp =a%mod;
	
	while(b)
	{
		if(b&1)
			anw = (anw * temp)%mod;
		b = b >> 1;
		temp = (temp * temp)%mod;
	}	
	return anw;
}	

int _binary(__int64 a,__int64 b,__int64 mod)
{
	__int64 anw = 1,temp =a%mod;
	
	while(b)
	{
		if(b&1)
			anw = (anw * temp)%mod;
		b = b >> 1;
		temp = (temp * temp)%mod;
	}	
	return (int)anw;
}	
   int ext_euclid(int a,int b,int &x,int &y)   
   {   
       int t,d;   
       if (b==0)
       {
           x=1;
           y=0;
           return a;
        }   
        d=ext_euclid(b,a%b,x,y);   
        t=x;   
        x=y;   
        y=t-a/b*y;   
        return d;   
   }     
int main()
{
	freopen("1.txt","r",stdin);
	freopen("2.txt","w",stdout);
	int i,j,k,p[100],n[100],right,left,a,b,temp,num=0;
	table();	
	while(scanf("%d%d",&a,&b)!=EOF)
	{
		if(a == 0)
		{
			printf("0\n");
			continue;
		}
		if(b == 0||a == 1)
		{
			printf("1\n");
			continue;
		}
		memset(n,0,sizeof(n));
		for(i = 0,j = 0;i < N&&a!=1 ;i++)
			if(a%prime[i] == 0)
			{
				p[j] = prime[i];
	            while(a%prime[i]==0)
	            {
					a = a / prime[i];
					n[j]++;
				}
				j++;
			}
		if( a!=1 )
		{
			p[j] = a;
			n[j] =1;
			j++;
		}					
		
		for(i = 0, right = 1 ,left = 1;i < j;i++)
		{
			if((p[i] - 1)%9901 == 0)
			{
				right = (right * (p[i] - 1))%(9901 * 9901);
				right = right /9901;
				left = (left * (_binary(p[i],n[i]*b+1,9901*9901)-1))%(9901*9901);
				left = left / 9901;
			}
			else
			{
				temp = p[i] - 1;
			    right = (right * temp)%9901;
				left = (left * (binary(p[i],n[i]*b+1,9901)-1))%9901;
			}
		}
		if(left < 0)
			left = left + 9901;
		ext_euclid(right,9901,temp,i);
		if(temp < 0)
			temp = temp + 9901;		   
		left = (left * temp)%9901;
		printf("%d %d\n",num++,left);
	}
	return 1;
}