Biject Inside

Practice

3.6 (36 votes)

Special numbers

Combinatorics

Easy Medium

Mathematics

Counting

Probability and statistics

Problem

63% Success 3170 Attempts 30 Points 1s Time Limit 256MB Memory 1024 KB Max Code

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\).

Sample Input

Sample Output

500000004
500000004
625000005

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 \(\dfrac{1}{2}\). 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 (\(2^2-1=3\) choices). In the latter case, Alice wins if and only if Bob chooses the set \(\{1,2\}\). So the probability is \(\dfrac{1}{2}\left(\dfrac{3}{4}+\dfrac{1}{4}\right)=\dfrac{1}{2}\). In case of \(n=3\), similarly exhausting the possibilities we can see that Alice wins with the probability \(\dfrac{5}{8}\).

Code Editor

You need to be logged in to access the code editor

Please wait while we load the editor

Results

Custom Input

Run your code to see the output

Submissions

Please login to view your submissions

You need to be logged in to access the code editor

Please wait while we load the editor

Results

Custom Input

Run your code to see the output