#include<stdio.h>
#include<math.h>
#include<string.h>
#include<algorithm>
#include<string>
#include<vector>
#include<iostream>
#include<cstring>
#define inf 0x3f3f3f3f
usingnamespace std;
#define ll long long
constint p=10007;
constint maxx=1e6+5;
ll a,b;
int prime[maxx];
bool vis[maxx];
int cnt;
void init()///欧拉筛{
    cnt=0;
    memset(vis,true,sizeof(vis));
    vis[0]=vis[1]=false;
    for(int i=2;i<=maxx;i++)
    {
        if(vis[i])
            prime[cnt++]=i;
        for(int j=0;j<cnt && prime[j]*i<=maxx;j++)
        {
            vis[ i*prime[j] ]=false;
            if( i%prime[j]==0 ) break;///prime[j]必定是prime[j]*i和i的最小质因子        }
    }
}
ll sum(ll n)///立方和公式{
   return ( (n*n+n)/2 )%p * ( (n*n+n)/2 )%p;
}

int main()
{
    init();
    int x=0;
    while(scanf("%lld%lld",&a,&b)!=EOF)
    {
        ll ans=1;
        if(vis[a])//a是素数，则直接求,节省时间
            ans=sum(1+b);
        else
        {//prime[i]*prime[i]<=a;不加就会超时，大素数的因子一般只有一个，没必要一个一个找,也可以改成!vis[a],都是避免多次循环找大素数for(int i=0; i<cnt && prime[i]*prime[i]<=a; i++)
            {
                int num=0;
                if(a==1) break;
                while(a%prime[i]==0)
                {
                    a=a/prime[i];
                    num++;
                }
                if(num!=0)
                {
                    ans*=sum(num*b+1);//积性函数
                    ans%=p;
                }
            }
            if(a!=1)///应对大素数的情况            {
                ans*=sum(b+1);
                ans%=p;
            }
        }
        printf("Case %d: %lld\n",++x,ans%p);
    }
    return0;
}
/*
手撸36=2^2 * 3^2  ans=(1^3 + 2^3 +3^3)^2=1296
36的因子有    1  2  3  4  6  9  12  18  36
对应的因子数  1  2  2  3  4  3  6   6   9
累加后也是1296
*/