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 pi 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≤T≤105.
- Each of the next T lines contains a positive integer n, the number Alice and Bob agree on, satisfying 1≤n≤1015.
Output Format
- For each game, print a single integer on a line: the probability that Alice wins modulo 109+7.
Note: It is guaranteed that the probability can be expressed as a rational number that exists modulo 109+7.
In case of n=1, Alice can only choose the permutation p=[1]. Alice wins if Bob chooses the subset {1} and loses if Bob chooses the empty subset {}. So the probability that Alice wins is 12.
In case of n=2, Alice can choose either p=[1,2] or p=[2,1]. In the former case, Alice wins if Bob chooses anything except the empty set (22−1=3 choices). In the latter case, Alice wins if and only if Bob chooses the set {1,2}. So the probability is 12(34+14)=12.
In case of n=3, similarly exhausting the possibilities we can see that Alice wins with the probability 58.
