Bob has a not even coin, every time he tosses the coin, the probability that the coin's front face up is $\frac{q}{p}\ (\frac{q}{p} \le \frac{1}{2})$
The question is, when Bob tosses the coin $k$ times, what's the probability that the frequency of the coin facing up is even number.
If the answer is $\frac{X}{Y}$, because the answer could be extremely large, you only need to print $(X * Y^{-1}) \mod (10^9+7)$.

First line an integer $T\ (T≤100)$, indicates the number of test cases.
Then Each line has $3$ integer $p,q,k\ (1\le p,q,k \le 10^7)$ indicates the $i$-th test case.

For each test case, print an integer in a single line indicates the answer.