E. Permutation XORpectation
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

We define the score of a permutation $$$p$$$ of length $$$n$$$ as following : $$$$$$ \sum_{i=2} ^n p_i \oplus p_{i-1} $$$$$$

Given $$$n$$$, find the expected value of the score of a random permutation of length $$$n$$$, modulo $$$10^9+7$$$.

Formally, let $$$M=10^9+7$$$. It can be shown that the answer can be expressed as an irreducible fraction $$$\frac{p}{q}$$$, where $$$p$$$ and $$$q$$$ are integers and $$$q\not\equiv 0(mod M)$$$. Output the integer equal to $$$p \cdot q^{-1} mod M$$$. In other words, output such an integer $$$x$$$ that $$$0 \leq x \lt M$$$ and $$$x \cdot q \equiv p (mod M)$$$.

Input

The first line contains a single integer $$$tc :\ (1 \le tc \le 10^5)$$$ — the number of testcases.

The only line of each testcase contains a single integer $$$n \: (1 \le n \le 10^{9})$$$.

Output

For each testcase, print the expected value of the score of a random permutation of length $$$n$$$, modulo $$$10^9+7$$$.

Example
Input
4
1
2
4
882
Output
0
3
12
476632137