SPOJ-INTSUB: Interesting Subset

杂

Description

You are given a set X = {1, 2, 3, 4, … , 2n-1, 2n} where n is an integer. You have to find the number of interesting subsets of this set X.

A subset of set X is interesting if there are at least two integers a & b such that b is a multiple of a, i.e. remainder of b divides by a is zero and a is the smallest number in the set.

Input

The input file contains multiple test cases. The first line of the input is an integer T(<=30) denoting the number of test cases. Each of the next T lines contains an integer 'n' where 1<=n<=1000.

Output

For each test case, you have to output as the format below:

Case X: Y

Here X is the test case number and Y is the number of subsets. As the number Y can be very large, you need to output the number modulo 1000000007.

Example

Input

3
1
2
3

Output

Case 1: 1
Case 2: 9
Case 3: 47

题意： t组数据，每组输入一个n，代表一个包含数字1到2n的集合，问这个集合x中有多少个有趣的子集,对结果取模。有趣的子集定义是：这个子集中的a是当中最小的数，子集中一定包含一个a的倍数（不含a本身）。
比如n为2，集合中有数字1，2，3，4；如果选1作为a，那么有趣的子集有：{1，2}，{1，3}，{1，4}，{1，2，3}，{1，2，4}，{1，3，4}，{1，2，3，4}；选择2为a，有{2，4}，{2，3，4}；一共九个。

分析：因为集合中一定存在n的倍数，那么a只能取到2n个数当中的前n个。
若取的a的下标为i，那么从i+1到2n中一共有x=2*n/i-1为a的倍数，对应有y=2*n-i-x个数不是a的倍数。
选择所有a的倍数有$C_x^1+C_x^2+...C_x^x$种选择，即$2^x-1$；所有非a的倍数同理有$2^y-1$种，非a的倍数和a倍数组合起来即相乘。使用快速幂计算。

• 代码：

#include<stdio.h>
#include<algorithm>
#define LL long long
using namespace std;
const int MOD=1000000007;
LL quick(LL x,LL m,LL n)//x^m%n
{
    LL ans=1;
    while(m>0)
    {
        if(m%2==1)
            ans=ans*x%n;
        x=x*x%n;
        m=m/2;
    }
    return ans;
}
int main()
{
    int t,n,o=0;
    LL ans;
    scanf("%d",&t);
    while(t--)
    {
        ans=0;
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
        {
            LL x=2*n/i-1;
            LL y=2*n-i-x;
            LL m=quick(2,x,MOD)-1;
            ans+=m;
            ans=(ans+(m*(quick(2,y,MOD)-1))%MOD)%MOD;
        }
        printf("Case %d: %lld\n",++o,ans);
    }
    return 0;
}