lightoj1054

CODE

#include <iostream>
#include <cstdio>

using namespace std;
typedef long long LL;
const int mod = 1e9+7;
bool vis[50000];
int cnt,prime[50000],ncase;
LL n,m;
LL qp(LL a,LL b)
{
        LL res=1;
        while(b)
        {
                if(b&1)res=res*a%mod;
                b>>=1;
                a=a*a%mod;
        }
        return res;
}
int main()
{
        for(int i=2;i<50000;i++) if(!vis[i])
        {
                prime[cnt++]=i;
                for(long long j=1ll*i*i;j<50000;j+=i)
                        vis[(int)j]=1;
        }
        int t;
        scanf("%d",&t);
        while(t--)
        {
                scanf("%lld %lld",&n,&m);
                LL sum=1;
                for(int i=0;i<cnt&&n!=1;i++)
                {
                        LL time=0;
                        while(n%prime[i]==0)
                        {
                                time++;
                                n/=prime[i];
                        }
                        if(time)
                        {
                              //  cout << prime[i]<<' '<<time;
                                time*=m;
                                LL tp=(qp(prime[i],time+1)-1+mod)%mod;
                                tp=tp*qp((prime[i]-1+mod)%mod,mod-2)%mod;
                                sum=sum*tp%mod;
                               // cout << ' '<<tp<<endl;
                        }
                }
                if(n>1)
                {
                        LL tp=(qp(n,m+1)-1+mod)%mod;
                        tp=tp*qp((n-1+mod)%mod,mod-2)%mod;
                        sum=sum*tp%mod;
                }
                cout <<"Case "<<++ncase<<": "<<sum<<endl;

        }
        return 0;
}