TOUGH - Bits. Exponents and Gcd


Rastas's has been given a number n. Being weak at mathematics, she has to consider all the numbers from 1 to 2n - 1 so as to become perfect in calculations. (You can assume each number is consider as a soldier).

We define the strength of number i as the number of set bits (bits equal to 1) in binary representation of number i.

If the greatest common divisor of numbers a and b is gcd(a, b),

Rastas would like to calculate the function S which is equal to: 

As the friend of Rastas, it's your duty to calculate S modulo 109 + 7.

Input

The first line of the input contains the number of test cases, T. Each of the next T lines contains an integer n, as mentioned in the question.

Output

For each value of n given, find the value of the function S.

Constraints

Sum of n over all test cases doesn't exceed 2500.

Example

Input:
3 
1 
2 
5

Output:
0 
3
680

hide comments
adi100: 2019-05-23 16:40:50

Nice Problem, enjoyed solving it.

azam_9: 2016-02-06 07:34:14

getting tle..any suggestions??

REPLY-> Your solution is brute force. Try something else.

Last edit: 2016-02-06 08:54:35
(Tjandra Satria Gunawan)(曾毅昆): 2016-02-06 00:10:28

Nice math problem ;-)


Added by:likecs
Date:2016-02-05
Time limit:1s
Source limit:10000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY
Resource:Own problem