A segment tree is Little L's favorite data structure, and it can efficiently solve many practical problems.

Given a positive integer $n$, Little L constructs a segment tree with indices in the integer interval $[1, n]$: The initial segment tree consists of only one node $[1, n]$. For a node $[L, R]$, if $L < R$, let $mid = \lfloor \frac{L+R}{2} \rfloor$ (where $\lfloor x \rfloor$ denotes the largest integer not exceeding $x$). Little L then creates two child nodes $[L, mid]$ and $[mid + 1, R]$ for this node.

Little L defines a function $cover(a, b)$ ($1 \le a \le b \le n$) as the minimum number of segment tree nodes required to cover the interval $[a, b]$ without overlap or omission.

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

Specifically, there are $\frac{n(n+1)}{2}$ distinct sub-intervals in $[1, n]$. If Little L selects one sub-interval $[A, B]$ uniformly at random from these $\frac{n(n+1)}{2}$ sub-intervals, then Little L considers the expected value of $cover(A, B)$ to be useful for evaluating the performance of this segment tree.

Little L asks you to help him calculate the product of the expected value of $cover(A, B)$ and $\frac{n(n+1)}{2}$, modulo $1,000,000,007$. It can be shown that this result is always an integer.

Input

Read data from standard input. The first line contains a positive integer $T$ ($1 \le T \le 1000$), representing the number of test cases. The next $T$ lines each contain a positive integer $n$ ($1 \le n \le 10^{18}$), representing the $i$-th test case.

Output

Output to standard output. $T$ lines, where the $i$-th line ($1 \le i \le T$) contains an integer representing the answer for the $i$-th test case.

Examples

Input 1

1
3

Output 1

7

Note

$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 expected value of $cover(A, B)$ is $\frac{1+1+1+1+2+1}{6} = \frac{7}{6}$.