You are provided a number $s$. In one step, a number $a$ is randomly selected from the interval $[0,N]$ and $s$ is replaced by $s\oplus a$ where $\oplus$ 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.
You can represent the answer as a rational fraction $\frac{P}{Q}$ with $Q>0$. To provide the answer, you should print $P⋅Q^{-1}\mod(10^9+7)$.

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\leq t\leq20000$

$0\le n,k,s\le10^9$

$1 \le t \le 20000$