E. Generational Triplets
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an integer $$$n$$$. Find the number of triplets of integers $$$(a, b, c)$$$ such that:

  • $$$1 \le a \lt b \lt c \le n$$$;
  • $$$a$$$, $$$b$$$, and $$$c$$$ form an arithmetic progression (i.e., $$$b - a = c - b$$$);
  • $$$a \oplus b \oplus c = 0$$$, where $$$\oplus$$$ denotes the bitwise XOR operation.
As the answer may be huge, you are only asked to output the answer modulo $$$10^9+7$$$.
Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

Each test case contains a single integer $$$n$$$ ($$$3 \le n \le 10^{18}$$$).

Output

For each test case, output a single integer — the number of valid triplets $$$(a, b, c)$$$ modulo $$$10^9 + 7$$$, on a separate line.

Example
Input
4
3
10
15
1000000000000000000
Output
1
2
5
353768760
Note

In the first testcase, for $$$n = 3$$$, the only valid triplet is $$$(1, 2, 3)$$$. It satisfies the arithmetic progression condition since $$$2 - 1 = 3 - 2 = 1$$$, and it satisfies the XOR condition since $$$1 \oplus 2 \oplus 3 = 0$$$.

For larger values of $$$n$$$, make sure to output the answer modulo $$$10^9 + 7$$$.