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 XOR 2 = 2¹

3 XOR 1 = 2¹

2 XOR 3 = 2⁰

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¹⁵).

Output

For each case a number of pair module 1000000007.

Example

Input:
3
1

2

3
Output:
1

2

4