You are provided a number s . In one step, a number is randomly selected from the interval [0,N] and s is replaced by s ⊕ a where ⊕ is the Bitwise XOR operation.
Determine the expected value of s after k steps modulo .10^9 + 7
There are multiple test cases in a single input file.
Input format • First line: An integer t denoting the number of test cases • Each test case consists of three integers n,k , and s in a single line Output format For each test case, print the answer in a new line. Constraints
1<=t <= 20000 0<= n,k,s<=10^9
SAMPLE INPUT
2
3 1 0
4 2 1
SAMPLE OUTPUT
500000005 320000005
Consider the distribution of each bit of the output separately.
Do we need to use concept of inverese modulo in this?
Yes, to do the calculations.
By the way, you should post a link to the original source where you found this problem when asking for help (https://mirror.codeforces.com/blog/entry/64993 recommends this).
This was a question from ongoing contest in Hackerearth July Circuits.