All Tracks>Problem
Biject Inside
★★★★★

3.6

36 votes
Special Numbers, Combinatorics, Easy-Medium, Mathematics, Counting, Probability and Statistics
Problem

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. 

Sample Input
3
1
2
3
Sample Output
500000004
500000004
625000005
Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

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. 

Contributers:
Editor Image

?