文理学院程序设计在线练习


FeiZhai happy number

Time Limit: 1 Second(s)    Memory Limit: 32 MB

Total Submission(s): 10   Accepted Submission(s): 6
Problem Description

As a Standard Feizhai, Lily can get happiness from different things everyday. Today he notice that he can get one point of happiness everytime he discover a pair of number as (i,j) which satisfies this equation “i+j = i|j” ( ‘|’ means bit-operation OR).Now he wants to know how many point of happiness he can get from all number in [1, 2^k].
If you think the answer is larger than 1e9+7, please output the answer mod 1e9+7.

Input

The first line contains a T which means the number of data sets.
In each data set:
one line contains one integers k.
T <= 128
k <= 128

Output

for each data set, output answer in one line.

Sample Input
2
1
10
Sample Output
2
59048
Hint

you can use every number within the given range as many times as you want but notice that only first discover of target can generate one happiness.
you can think (i,j) and (j,i) are different if and only if i != j.

Source

2018市赛