CF2252E Generational Triplets

给定一个整数 $n$。求满足以下条件的三元组 $(a,b,c)$ 的个数： - $1 \le a < b < c \le n$； - $a,b,c$ 构成等差数列（即 $b-a=c-b$）； - $a \oplus b \oplus c = 0$，其中 $\oplus$ 表示[按位异或运算](https://en.wikipedia.org/wiki/Bitwise_operation#XOR)。 由于答案可能很大，你只需要输出答案对 $10^9+7$ 取模后的结果。

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。接下来是每个测试用例的描述。 每个测试用例包含一个整数 $n$（$3 \le n \le 10^{18}$）。

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

在第一个测试用例中，$n=3$ 时，唯一合法的三元组是 $(1,2,3)$。它满足等差数列条件，因为 $2-1=3-2=1$，也满足异或条件，因为 $1 \oplus 2 \oplus 3 = 0$。 对于更大的 $n$，请确保输出答案对 $10^9+7$ 取模。