Alice and Bob play a lot of games. Here's what a game looks like. At first they agree on a positive integer \(n\). Then they do the following simultaneously: Alice writes down a permutation \(p\) of the first \(n\) positive integers, and Bob writes down a (possibly empty) subset \(S\) of the first \(n\) positive integers. Alice wins if there is at least one index \(i\) such that both \(i\) and \(p_i\) are inside the set \(S\) that Bob picked.

Assuming they both make their choices uniformly at random (that is, Alice chooses a random permutation and Bob chooses a random subset), what is the probability that Alice wins?

Input Format

The first line contains a positive integer \(T\), the number of games played, satisfying \(1\le T\le 10^5\).
Each of the next \(T\) lines contains a positive integer \(n\), the number Alice and Bob agree on, satisfying \(1\le n\le 10^{15}\).

Output Format

For each game, print a single integer on a line: the probability that Alice wins modulo \(10^9 + 7\).

Note: It is guaranteed that the probability can be expressed as a rational number that exists modulo \(10^9+7\).