T599232 猫猫虫的序列
题目描述
猫猫虫有一个定义如下的数列：
$$
a_{n} =
\begin{cases}
0 & n = 1 \\
a_{\left\lfloor \frac{n}{2} \right\rfloor} + (-1)^{\frac{n(n + 1)}{2}} & n \geq 2
\end{cases}
$$
猫猫虫要求 saki 计算该数列前 $n$ 项绝对值的和，即求：
$$
\sum_{i=1}^{n} |a_{i}|
$$
输出答案对 $10^{9} + 7$ 取模后的结果。saki 做不出来，你能帮帮她吗？
输入格式
每个测试点包含多组测试数据。第一行给定一个整数 $T(1\leq T\leq 10^6)$，表示测试数据组数。
对于每组测试数据，一行给定一个整数 $n(1 \leq n \leq 10^{18})$ 表示数列的长度。
输出格式
对于每组测试数据，输出一行一个整数表示对应答案对 $10^9 + 7$ 取模后的结果。
说明/提示
本题的输入输出量较大，请注意所使用的输入输出方式。