# Random OR Solution Codechef

## Random OR Solution Codechef

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 SS 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⋅Q−1(mod 109+7), where Q−1 denotes the modular multiplicative inverse of Q with respect to 109+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 109+7109+7.

Constraints

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

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

• 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 ∑k=1∞k⋅2−k, which equals 2.

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

### SOLUTION

Program: Random OR Solution in C++

``````#include <bits/stdc++.h>
using namespace std;
long long mod = 1e9+7;
void calc_gcd(long long a, long long n, long long* x, long long* y){
if(a==0){
*x = 0;
*y = 1;
return;
}
long long X, Y;
calc_gcd(n%a, a, &X, &Y);
*x = Y - (n/a)*X;
*y = X;
return;
}
long long inverse(long long a, long long n){
long long x, y;
calc_gcd(a, n, &x, &y);
while(x<0) x+=n;
return x%n;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
long long t, n;
cin >> t;
while(t--){
cin >> n;
long long alt[] = {mod-1, 1};
long long comb = 1;
long long ans = 0;
long long pow2 = 1;

for(int i=1;i<=n;i++){
comb = (comb*(n-i+1))%mod;
comb = (comb*inverse(i, mod))%mod;
pow2 *= 2;
pow2 %= mod;

long long cur = (alt[i&1]*comb)%mod;
cur = (cur*pow2)%mod;
cur = (cur*inverse((pow2-1+mod)%mod, mod))%mod;
ans = (ans+cur)%mod;
}
cout << ans << "\n";
}
return 0;
}``````