Dorel, elev în clasa a X-a, a început recent să experimenteze cu algoritmi de plasare a $B$ bile identice în $C$ cutii! El a încercat să analizeze în câte moduri poate plasa cele $B$ bile în cele $C$ cutii alese astfel încât pentru o constantă $K$ aleasă algoritmul scris de el pe hârtie să nu ruleze la infinit. Algoritmul lui poate fi găsit scris în pseudocod mai jos:

poz ← 1
sum ← 0
cât timp poz <= c:
    cât timp sum != k:
        sum ← sum + nrbile[poz] + 1
		poz ← poz + 1
	sum ← 0

Cerință

Pentru $B$ bile, $C$ cutii și o constantă $K$, determinați în câte moduri putem plasa bilele în cutii în așa fel încât algoritmul prezentat mai sus nu rulează la infinit. Cum acest numar poate fi foarte mare, Dorel va roaga sa aflati restul impartirii lui la $10^9+7$

Date de intrare

Pe prima linie a fișierului de intrare dorel.in se găsește numărul $T$, care prezintă numărul de teste. Apoi, pe următoarele $T$ linii se vor afla câte 3 numere $B, C$ și $K$ cu semnificația de mai sus. Testele din input sunt independente unul față de celălalt.

Date de ieșire

În fișierul dorel.out se vor afișa $T$ numere pe câte o linie separată fiecare, unde pe linia $i$ din output se va afla răspunsul la al $i$-lea test modulo $10^9+7$.

Restricții și precizări

• $1 \leq T \leq 2 \cdot 10^5$
• $1 \leq B, C, K \leq 10^6$
• Conform regulamentului OJI, teste vor fi evaluate individual, deci nu este necesară trecerea tuturor testelor pentru primirea punctajului pe subtaskul aferent.

Exemplul 1

dorel.in

6
3 3 3
1 5 6 
10 10 10
5 8 1
10 2 4
961 423 346

dorel.out

4
5
43758
0
0
434187092

Explicație

Pentru cazul $B = 3, C = 3, K = 3$ avem următoarele configurații valabile posibile:

• $0, 1, 2$
• $1, 0, 2$
• $2, 0, 1$
• $2, 1, 0$

Pentru cazul $B = 1, C = 5, K = 6$ avem următoarele configurații valabile posibile:

• $1, 0, 0, 0, 0$
• $0, 1, 0, 0, 0$
• $0, 0, 1, 0, 0$
• $0, 0, 0, 1, 0$
• $0, 0, 0, 0, 1$