Random OR Solution|Codesheff February long 2022- Division 3(Rated)

 Chef is playing a game, which he starts with a score of S=0. He also has an integer N.

In one move, Chef does the following:

• Uniformly randomly pick an integer X between 0 and 2N−1 (inclusive of both ends)
• Update his score as S→S∣X, where ∣ denotes the bitwise OR operation

For example, if Chef's current score is S=6 and he picks X=10, his new score is 6∣10=14.

Chef stops when his score S becomes equal to 2N−1. What is the expected number of moves Chef performs?

Output the answer modulo 109+7. That is, the answer can be expressed as a fraction P/Q, where gcd(Q,109+7)=1. Print P\cdot Q^{-1} \pmod{\ 10^9 + 7}, where Q^{-1} denotes the modular multiplicative inverse of Q with respect to 10^9 + 7.

Input Format

• The first line of input contains an integer T, denoting the number of test cases. The description of T test cases follows.
• Each test case contains a single integer N.

Output Format

For each test case, output on a new line the expected number of moves Chef performs, modulo 10^9 + 7.

Constraints

• 1 \leq T \leq 100
• 1 \leq N \leq 3 \cdot 10^5
• Sum of N over all test cases do not exceed 3 \cdot 10^5

Subtasks

Subtask 1 (30 points):

• 1 \leq N \leq 10^3
• Sum of N over all test cases doesn't exceed 10^3

Subtask 2 (70 points):

• Original constraints

Sample Input 1 

3
1
2
100

Sample Output 1 

2
666666674
328238032

Explanation

Test case 1: In each move, Chef chooses either 0 or 1, each with a probability of 1/2. The game ends as soon as Chef chooses 1. Thus, the probability that the game takes exactly k moves is 2^{-k}.

The required expected value is then \displaystyle\sum_{k=1}^\infty k\cdot 2^{-k}, which equals 2.

Test case 2: In each move, Chef chooses an integer in [0, 3]. The answer is 8/3.

Solution: