PAN1 - Panelák 1

Developerovi sa podarilo kúpiť lukratívny pozemok na stavbu nového paneláku s bočným výhľadom na centrum mesta. Panelák chce postaviť z jedného štandardizovaného typu bytu, pričom v každom vchode chce predať aj luxusný byt, teda taký, čo má výhľad na centrum mesta (to znamená, že vo výhľade mu nemôžu brániť byty z vedľajšieho vchodu). Pomôžte mu vypočítať počet rôznych možností postavenia paneláku pre daný počet bytových jednotiek a minimálny počet luxusných bytov v každom vchode. Panelák je postupnosť vchodov zložených z jednotlivých bytov.

Panelák s 3 vchodmi a 1 luxusným bytom v každom vchode:

Panelák s 3 vchodmi a počtami luxusných bytov: 1, 2 a 1

Toto nie sú korektné paneláky:

Vstup

Prvý riadok vstupu obsahuje číslo n určujúce počet testovacích sád (1 ≤ n ≤ 5000). Každý z nasledujúcich n riadkov obsahuje tri medzerou oddelené celé čísla - počet bytov b, počet vchodov v a minimálny počet luxusných bytov vo vchode l.

Výstup

Pre každú testovaciu sadu vypíšte na samostatnom riadku jedno číslo – počet možností, ako postaviť panelák. Keďže toto číslo môže byť veľmi veľké, vypíšte jeho zvyšok po delení 1 000 007.

A1

1 ≤ b ≤ 100
1 ≤ v ≤ 15
l = 1

A2

1 ≤ b ≤ 500
1 ≤ v ≤ 35
1 ≤ l ≤ 35

Príklad 1 (PAN1, PAN2)

Vstup:

3
4 1 1
5 2 1
7 3 1

Výstup:

1
2
1

Príklad 2 (PAN2)

Vstup:

2
20 3 2
20 3 3

Výstup:

10
2

Pri poslednom vstupe sú možnosti 3+7+10 a 3+6+11.