CF2252E.Generational Triplets

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

给你一个整数 $n$。请找出满足以下条件的整数三元组 $(a, b, c)$ 的个数：

• $1 \le a \lt b \lt c \le n$；
• $a$、$b$ 和 $c$ 构成等差数列（即 $b - a = c - b$）；
• $a \oplus b \oplus c = 0$，其中 $\oplus$ 表示按位异或运算。

由于答案可能非常大，你只需输出答案对 $10^9+7$ 取模的结果。

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

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。随后是测试用例的描述。

每个测试用例包含一个整数 $n$（$3 \le n \le 10^{18}$）。

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

对于每个测试用例，输出一行一个整数——满足条件的三元组 $(a, b, c)$ 的个数对 $10^9 + 7$ 取模的结果。

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

在第一个测试用例中，当 $n = 3$ 时，唯一有效的三元组是 $(1, 2, 3)$。它满足等差数列条件，因为 $2 - 1 = 3 - 2 = 1$；同时也满足异或条件，因为 $1 \oplus 2 \oplus 3 = 0$。

对于更大的 $n$ 值，请确保输出答案对 $10^9 + 7$ 取模的结果。