LOVINGPW - Loving Power

no tags 

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 = 2z   where z>=0.

See that for N = 3 :

0 XOR 1 = 20

0 XOR 2 = 21

3 XOR 1 = 21

2 XOR 3 = 20

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 (1015).

Output

For each case a number of pair module 1000000007.

Example

Input:
3
1
2
3
Output:
1
2
4

hide comments
:(: 2015-02-05 13:22:46

Good one... :) @Ouditchya thanks for the test case :)

Vamsi Krishna Avula: 2015-01-19 19:40:48

good problem :)

[deleted]: 2013-06-19 12:09:35

my best one till now...:D
bitwise operation is the best way

Aradhya: 2013-06-05 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: 2013-06-05 13:04:36

for playgroup kids :D

Aditya Bahuguna: 2013-06-02 10:42:32

Real Nice Prob (y).

Man Mohan Mishra: 2013-06-01 08:50:58

huh... finally solved it.
problem is really nice , I made my own formula for the task.

Rajarshi Sarkar: 2013-05-31 12:53:55

1's and 0's everywhere :D

shiva_hellgeek: 2013-05-16 07:12:59

finally got AC.
It was an excellent problem learned a lot from this one.
thanks to problem setter

Ouditchya Sinha: 2013-04-24 11:01:49

Not reading the problem correctly caused me many WAs, the sequence is indeed very nice... :)
O/P for 10^15 is 227182119.

Finally AC in 0.00s. :)

Last edit: 2013-07-18 15:39:53

Added by:olimpoUS
Date:2013-02-17
Time limit:0.171s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM32-GCC ASM64 MAWK BC C-CLANG CPP14-CLANG CPP14 COBOL COFFEE D-DMD D-CLANG DART ELIXIR FANTOM FORTH GOSU GRV JS-MONKEY KTLN NIM OBJC OBJC-CLANG OCT PICO PROLOG PYPY R RACKET RUST CHICKEN SQLITE SWIFT UNLAMBDA VB.NET
Resource:Luis Giro