XOR Subset

Fermat’s little theorem states that if p is a prime number, then for any integer a, the number (ap −a) is an integer multiple of p. In the notation of modular arithmetic, this is expressed as ap ≡ a(mod p) Forexample,ifa=2andp=7,27 =128,and128−2=7×18isanintegermultipleof7. Wecan also write 128%7 = 2, here % is the modulo operator used in C/C++ or Java. If a is not divisible by p, Fermat’s little theorem is equivalent to the statement that ap−1 − 1 is an integer multiple of p, or in symbols ap−1 ≡ 1(mod p) Forexample,ifa=2andp=7then26 =64and64−1=63isamultipleof7. Wecanalsowrite 64%7 = 1. You are given a set S which contains 1 to N. You want to find two subsets of S, X and Y such that the following conditions are met:

1. X ∩ Y = ∅
2. Let bitwise XOR of every element of X equals U and Y equals V . U must be less than or equal to V . You want to find out number of ways you can choose such subset X and Y . Two ways (X1, Y1) and (X2, Y2) will be equal if X1 equals X2 and Y1 equals Y2 or X1 equals Y2 and Y1 equals X2. For example is S = {1, 2}, the ways are:
3. X = ∅, Y = ∅. [U = 0, V = 0]
4. X = ∅, Y = {1}. [U = 0, V = 1]
5. X = ∅, Y = {1, 2}. [U = 0, V = 1 ∧ 2 = 3, (∧ means bitwise XOR in C/C++/Java)] 4. X = ∅, Y = {2}. [U = 0, V = 2]
6. X = {1}, Y = {2}. [U = 1, V = 2] Now, given N, you need to find the number of ways you can choose two subsets of S such that the 2 conditions meet, modulo 1000000007 (109 + 7). Input First line contains T (T ≤ 100), the number of test cases. Each of the next T lines each contains an integer N (0 ≤ N < 1010000). Output For each case print one line, ‘Case C: W’, where C is the case number, and W is the required answer for that case.

2/2 Sample Input 2 2 3 Sample Output Case 1: 5 Case 2: 14