LOVINGPW  Loving Power
Angel Luis is now getting math class. His teacher is teaching to him the XOR operation.
0 XOR 0 = 0
0 XOR 1 = 1
1 XOR 0 = 1
1 XOR 1 = 0
When is a number with more than a bit it operation is made to all bits. The teacher write two number x,y (0<=x<=N and 0<=y<=N) and make the XOR operation betwen x and y, Angel Luis would like to know how many pairs x,y such x XOR y = 2^{z }where z>=0.
See that for N = 3 :
0 XOR 1 = 2^{0}
0 XOR 2 = 2^{1}
3 XOR 1 = 2^{1}
2 XOR 3 = 2^{0}
So there is 4 pairs.
Given N you should return how many pair module 1000000007.
Input
First line a number t (number of cases) each t line will have a number N
t<=100
N<=1000000000000000 (10^{15}).
Output
For each case a number of pair module 1000000007.
Example
Input:
3
1
2
3
Output:
1
2
4
hide comments
:(:
20150205 13:22:46
Good one... :) @Ouditchya thanks for the test case :) 

Vamsi Krishna Avula:
20150119 19:40:48
good problem :) 

[deleted]:
20130619 12:09:35
my best one till now...:D


Aradhya:
20130605 13:07:45
@rajarshi sarkar.. best comment i have seen so far.. after solving this i looked at your comment.. it directly points to the solution :) 

Aradhya:
20130605 13:04:36
for playgroup kids :D 

Aditya Bahuguna:
20130602 10:42:32
Real Nice Prob (y).


Man Mohan Mishra:
20130601 08:50:58
huh... finally solved it.


Rajarshi Sarkar:
20130531 12:53:55
1's and 0's everywhere :D 

shiva_hellgeek:
20130516 07:12:59
finally got AC.


Ouditchya Sinha:
20130424 11:01:49
Not reading the problem correctly caused me many WAs, the sequence is indeed very nice... :)

Added by:  olimpoUS 
Date:  20130217 
Time limit:  0.171s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM32GCC ASM64 MAWK BC CCLANG CPP14CLANG CPP14 COBOL COFFEE DDMD DCLANG DART ELIXIR FANTOM FORTH GOSU GRV JSMONKEY KTLN NIM OBJC OBJCCLANG OCT PICO PROLOG PYPY R RACKET RUST CHICKEN SQLITE SWIFT UNLAMBDA VB.NET 
Resource:  Luis Giro 