Description

The segment tree is Little L’s favorite data structure. It can efficiently solve many practical problems.

Given a positive integer $n$, Little L builds a segment tree whose indices belong to the integer interval $[1, n]$:

• Initially, the segment tree has only one node $[1, n]$.
• For a node $[L, R]$, if $L < R$, let $mid = \left[ \frac{L + R}{2} \right]$ (where $[x]$ denotes the greatest integer not exceeding $x$). Little L creates two child nodes for this node: $[L, mid]$ and $[mid + 1, R]$.

Little L defines a function $cover(a, b)$ ($1 \le a \le b \le n$), which means using several segment tree nodes to cover the interval $[a, b]$ without overlap and without omission. $cover(a, b)$ is the minimum possible number of segment tree nodes used.

Little L tries to use this segment tree to solve a complex problem, and wants to roughly evaluate the performance of this segment tree.

Specifically, the interval $[1, n]$ has $\frac{n (n + 1)}{2}$ different sub-intervals. If Little L randomly selects one sub-interval from these $\frac{n (n + 1)}{2}$ sub-intervals with equal probability, denoted as $[A, B]$, then Little L believes the expected value of $cover(A, B)$ can be used to evaluate the performance of this segment tree.

Little L wants you to help compute the result of $\mathbb{E}[cover(A, B)]$ multiplied by $\frac{n (n + 1)}{2}$ modulo $1, 000, 000, 007$. You may find that this result must be an integer.

Input Format

The first line contains a positive integer $T$ ($1 \le T \le 1000$), indicating the number of test cases.
The next $T$ lines follow. In the $i$-th line ($1 \le i \le T$), there is a positive integer $n$ ($1 \le n \le {10}^{18}$), indicating the value of $n$ for the $i$-th test case.

Output Format

Output $T$ lines. In the $i$-th line ($1 \le i \le T$), output one integer representing the answer for the $i$-th test case.

1
3

7

Hint

[Sample Explanation #1]

$cover(1, 1) = 1$, $cover(2, 2) = 1$, $cover(3, 3) = 1$, $cover(1, 2) = 1$, $cover(2, 3) = 2$, $cover(1, 3) = 1$. Therefore, the expectation of $cover(A, B)$ is $= \frac{1 + 1 + 1 + 1 + 2 + 1}{6} = \frac{7}{6}$.

[Source]

From the preliminary round of the 2021 Tsinghua University Student Algorithm Contest and Collegiate Invitational (THUPC2021).

Resources such as the editorial can be found at https://github.com/THUSAAC/THUPC2021-pre.

Translated by ChatGPT 5