SPOJ : Interesting Subset 想法题

INTSUB - Interesting Subset

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

题目链接

题意：给你一个n，让你求{1,2,3…2n-1,2n}这个集合里面有多少个子集满足：至少有两个元素a,b满足a%b==0且a小于b

解题思路：对每一个1-n中的数，我们总能找到一个数能整除它，因此我们只要对能整除它的进行排列组合且至少要有一个，对不能整除它的也进行排列组合，可以没有。最后相乘，全部加起来后 mod 1000000007 就是我们所要求的答案。