题目的意思是求 [西伽马(p+q)]其中lcm(p,q)=n。
又见数论呀。
其实这个题目很简单，考虑清楚了可以很简单的方法飘过。
我一开始是这样来考虑的。
对于每一个单独的质因子，如果为p，它的次数为x，那么在p和q中一定有一个为p^x，另一个为p^y（0<=y<=x)，只有这样才能保证lcm为p^x。
这样我们可以枚举第一个为p^x，第二个数就是等比数列求和了。
同时我们再枚举第二个为p^x，这样我们就又是等比数列求和了。。。。
这样我们每次分别计算每一个质因子，同时每一个质因子其实是相对独立的，所以我们最后只要做一次乘法就可以了。不过注意每一个质因子出现的次数哦。
嗯到了这里我们就可以知道了，不过对于每一个答案还是统计了两遍，所以要把多出来的减出来。
嗯，大概就是这样的。
但是A掉后，我好像又秒懂了更更简单的办法。诶，深坑啊。自己考虑考虑就知道啦。。。
这个是经过预处理之后才勉强A掉的，内牛满面啊。。。。。——————————
#include <iostream>
#include <cstring>
#include <cstdio>
#define ll long long
#define M 1000000007
using namespace std; ll t,c,p[],a[],cas=;
ll ans;
ll f1[],f2[],f3[]; ll power(ll x,ll y)
{
ll tot=;
while (y)
{
if (y&) tot=(tot*x)%M;
y>>=;
x=(x*x)%M;
}
return tot;
} ll mod(ll x)
{
if (x<M) return x;
x-=M;
if (x<M) return x;
return x-M;
} ll count(ll x)
{
ll A=,B=,F,G;
for (ll i=; i<=c; i++)
{
if (x&(<<(i-)))
{
F=(f1[i]*(a[i]+))%M;
G=((f2[i]-)*(f3[i]))%M;
}
else
{
F=((f1[i]-)*(f3[i]))%M;
G=(f1[i]*(a[i]))%M;
}
A=(A*F)%M;
B=(B*G)%M; //cout<<" a: & b: "<<A<<' '<<B<<endl;
}
return mod(A+B);
} ll over=power(,M-); int main()
{
scanf("%lld",&t);
while (t--)
{
ans=;
scanf("%lld",&c);
for (ll i=; i<=c; i++) scanf("%lld%lld",&p[i],&a[i]);
for (ll i=; i<=c; i++)
{
f1[i]=power(p[i],a[i]);
f2[i]=power(p[i],a[i]+);
f3[i]=power(p[i]-,M-);
}
//ans=count(1<<(c)-1); cout<<"ans : "<<ans<<endl;
for (ll i=; i<(<<c); i++) ans=mod(ans+count(i));
ll tep=;
for (ll i=; i<=c; i++) tep=(tep*f1[i])%M;
ans=mod(ans+*tep);
ans=(ans*over)%M;
if (ans<) ans+=M;
printf("Case %lld: %lld\n",++cas,ans);
}
return ;
}