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 a number has more than one bit, the operation is applied to all bits. The teacher write two numbers x, y (0 <= x, 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 are 4 pairs.

Given N you should return the number of pairs modulo 1000000007.

Input

First line contains number t - the number of cases. Following t lines will each 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