Jocuri cu Kdouri

Nu lăsa pe mâine ce poți face azi, lasă pe poimâine

Alice Elice l-a provocat pe Bob Glob la un joc. Alice Elice are două grămezi cu $P_1$ și $P_2$ cadouri. Înainte de a începe jocul, Alice aruncă un zar cu $N$ fețe și notează numărul rezultat cu $K$. Jocul constă în următoarele etape:

La inceput dacă $K$ este par atunci ea deschide toate cadourile din prima grămadă, iar dacă $K$ este impar atunci deschide toate cadourile din a doua grămadă. În următoarele ture, cei doi aleg alternativ cadouri, începând cu Bob. Jucătorul trebuie să deschidă din grămada rămasă între $1$ și $K$ cadouri. Cine nu poate deschide cel puțin un cadou pierde.

Cerință

Alice dorește și anul viitor multe cadouri, așa că vrea să afle probabilitatea să câștige jocul, considerând că cei doi joacă optim.

Date de intrare

Pe prima linie se dă $T$, numărul de teste. Pe următoarele $T$ linii se află $P_1$, $P_2$ și $N$.

Date de ieșire

Să se afișeze pentru fiecare dintre cele $T$ teste șansa de câștig modulo $10^9 + 7$ (vezi mai jos).

Restricții și precizări

• $0 \leq T \leq 10^3$
• $0 \leq P_1, P_2 \leq 10^9$
• $0 \leq N \leq 10^4$
• Presupunem că există un model de zar cu $N$ fețe.
• Dacă exprimăm probabilitatea ca Alice să câștige prin raportul $\frac{a}{b}$, atunci voi veți afișa $a \cdot b^{-1} \text{ mod } (10^9 + 7)$, unde $b^{-1}$ este inversul modular a lui $b$, modulo $10^9+7$.
• Cei doi joacă optim.

Exemplu

stdin

3
3 2 3
333625 453145 800
1 1 1

stdout

0
855000006
0

Explicație

Dacă zarul are valoarea $1$ atunci:

• Rămâne grămada $1$ cu $3$ cadouri $\rightarrow$ Alice pierde;

Dacă zarul are valoarea $2$ atunci:

• Rămâne grămada $2$ cu $2$ cadouri $\rightarrow$ Alice pierde;

Dacă zarul are valoarea $3$ atunci:

• Rămâne grămada $1$ cu $3$ cadouri $\rightarrow$ Alice pierde.