Fişierul intrare/ieşire:	hagi.in, hagi.out	Sursă	FMI No Stress 9
Autor	Usurelu Florian Robert	Adăugată de	FMI No Stress 9 •fminostress9
Timp execuţie pe test	0.1 sec	Limită de memorie	32768 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Hagi

Ajuns la inceput de cariera, Ianis Hagi da semne ca va deveni un mare fotbalist. In consecinta, Gica, curios din fire, doreste sa afle cum va arata traseul lui Ianis. Acesta calatoreste in indepartatul tinut iGorj pentru a-l intreba pe Bogdanel MIPS mai multe detalii despre viitorul fiului sau. Bogdanel ii prevesteste faptul ca Ianis, pana la finalul carierei, va juca la K echipe, marcand N goluri si dand M asisturi. Gica, ambitios, doreste sa afle numarul total de scenarii diferite ale carierei lui Ianis modulo 1.000.000.007.
Un scenariu (mod) este diferit de altul, daca exista o echipa i din cele K pentru care numarul de asisturi sau de goluri difera.

Date de intrare

Fişierul de intrare hagi.in contine pe prima linie 3 numere: K (numarul de echipe), N (numarul de goluri) si M (numarul de asisturi).

Date de ieşire

În fişierul de ieşire hagi.out va contine pe prima linie numarul total de scenarii diferite modulo 1.000.000.007.

Restricţii

• 1 ≤ K, N, M ≤ 1.000.000
• Pentru 10 puncte, 1 ≤ K, N, M ≤ 7
• Pentru alte 20 puncte, 1 ≤ K, N, M ≤ 50
• Pentru alte 30 puncte, 1 ≤ K, N, M ≤ 1.000

Exemplu

Explicaţie

Pentru primul exemplu, posibilitatile sunt urmatoarele:
-> la prima echipa: 0 goluri, 0 pase -- la a 2-a echipa: 2 goluri, 1 pasa ;
-> la prima echipa: 0 goluri, 1 pase -- la a 2-a echipa: 2 goluri, 0 pasa ;
-> la prima echipa: 1 goluri, 0 pase -- la a 2-a echipa: 1 goluri, 1 pasa ;
-> la prima echipa: 1 goluri, 1 pase -- la a 2-a echipa: 1 goluri, 0 pasa ;
-> la prima echipa: 2 goluri, 0 pase -- la a 2-a echipa: 0 goluri, 1 pasa ;
-> la prima echipa: 2 goluri, 1 pase -- la a 2-a echipa: 0 goluri, 0 pasa .

Cum se trimit solutii?