[Solution] Random OR solution codechef

Random OR solution codechef – Chef is playing a game, which he starts with a score of S=0S=0. He also has an integer NN.

In one move, Chef does the following:

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

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

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

Output the answer modulo 109+7109+7. That is, the answer can be expressed as a fraction P/QP/Q, where gcd(Q,109+7)=1gcd(Q,109+7)=1. Print PQ1(mod 109+7)P⋅Q−1(mod 109+7), where Q1Q−1 denotes the modular multiplicative inverse of QQ with respect to 109+7109+7.

Input Format

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

Output Format

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

Constraints

• 1T1001≤T≤100
• 1N31051≤N≤3⋅105
• Sum of NN over all test cases do not exceed 31053⋅105

• 1N1031≤N≤103
• Sum of NN over all test cases doesn’t exceed 103103

• Original constraints

Sample Input 1

3
1
2
100


Sample Output 1

2
666666674
328238032


Explanation

Test case 11: In each move, Chef chooses either 00 or 11, each with a probability of 1/21/2. The game ends as soon as Chef chooses 11. Thus, the probability that the game takes exactly kk moves is 2k2−k.

The required expected value is then k=1k2k∑k=1∞k⋅2−k, which equals 22.

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