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 numbers x, y (0 <= x <= N and 0 <= y <= N) and make the XOR operation between 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 the number of pairs modulo 1000000007.

Example

Input:
3
1
2
3
Output:
1
2
4