SP26301 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 2_n_ - 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.

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

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