学步园

//险过
#include<cstdio>
typedef long long ll;
const int maxn=5e6 + 7;
const ll mod=1e9 + 7;
int cnt[maxn];
int p2[maxn];

void init()   
{
	cnt[0]=0;
	int i,j;
	for(i=1;i<maxn;i++)
	{
		cnt[i] = (i/3 + (i&1?1:0))/2 ;  //b==c的个数 边长a<=b<=c
		cnt[i] += cnt[i-1] - (i&1?0:1)*i/4; // b<c的个数
		cnt[i] %= mod;
	}
	p2[1]=1;
	p2[2]=2;
	for(i=3;i<maxn;i++) //求(a,b,c)最大公约数为1的三角形个数
	{
		p2[i]=(p2[i-1]<<1)%mod;
		for(j=i+i;j<maxn;j += i)
		{
			cnt[j] = (cnt[j]-cnt[i]+mod)%mod;
		}
	}
}

int main()
{
	init();
	int n,id=0;
	while(~scanf("%d",&n))
	{
		int i;
		ll ans=0;
		for(i=1;i*i<=n;i++)
		{
			if(n%i==0)
			{
				ans = (ans + (ll)cnt[i]*p2[n/i]) % mod;
				if(i*i!=n)
				{
					ans = (ans + (ll)cnt[n/i]*p2[i]) % mod;
				}
			}
		}
		printf("Case %d: %I64d\n",++id,ans);
	}
	return 0;
}