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 . 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})). For each test case, output a single integer — the number of valid triplets ((a, b, c)) modulo (10^9 + 7), on a separate line. 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).