Chiaki Sequence Reloaded

题号：NC17339
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 128 M，其他语言256 M
64bit IO Format: %lld

题目描述

Chiaki is interested in an infinite sequence a₁, a₂, a₃, ..., which defined as follows:
$a_n=\begin{cases}0 & n = 1 \\ a_{\lfloor \frac{n}{2} \rfloor} + (-1)^{\frac{n(n+1)}{2}} & n \ge 2\end{cases}$
Chiaki would like to know the sum of the first n terms of the sequence, i.e. $\sum\limits_{i=1}^{n}|a_i|$ . As this number may be very large, Chiaki is only interested in its remainder modulo (10⁹ + 7).

输入描述:

There are multiple test cases. The first line of input contains an integer T (1 ≤ T ≤ 10⁵), indicating the number of test cases. For each test case:
The first line contains an integer n (1 ≤ n ≤ 10¹⁸).

输出描述:

For each test case, output an integer denoting the answer.

示例1

输入

复制

输出

复制