Random OR solution codechef – Chef is playing a game, which he starts with a score of. He also has an integer .
In one move, Chef does the following:
- Uniformly randomly pick an integer between and (inclusive of both ends)
- Update his score as bitwise OR operation , where denotes the
For example, if Chef’s current score isand he picks , his new score is .
Chef stops when his scorebecomes equal to . What is the expected number of moves Chef performs?
Output the answer modulo. That is, the answer can be expressed as a fraction , where . Print , where denotes the modular multiplicative inverse of with respect to .
- The first line of input contains an integer , denoting the number of test cases. The description of test cases follows.
- Each test case contains a single integer .
For each test case, output on a new line the expected number of moves Chef performs, modulo.
- Sum of over all test cases do not exceed
Subtask 1 (30 points):
- Sum of over all test cases doesn’t exceed
Subtask 2 (70 points):
- Original constraints
Sample Input 1
3 1 2 100
Sample Output 1
2 666666674 328238032
Test case: In each move, Chef chooses either or , each with a probability of . The game ends as soon as Chef chooses . Thus, the probability that the game takes exactly moves is .
The required expected value is then equals ., which
Test case: In each move, Chef chooses an integer in . The answer is .