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.

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$.