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