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](https://en.wikipedia.org/wiki/Bitwise_operation#XOR). As the answer may be huge, you are only asked to output the answer modulo $ 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} $ ).

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