hagi

Hagi

== include(page="template/taskheader" task_id="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 666013.
Un mod este diferit de altul, daca exista o echipa i din cele K pentru care numarul de asisturi sau de goluri difera.

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.

h2. Date de intrare

h2. 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.009.

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

h2. 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 ≤ 2.000$

* Pentru alte 30 puncte, $1 ≤ K, N, M ≤ 1.000$

h2. Exemplu
table(example). |_. hagi.in |_. hagi.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|

| 2 2 1 | 6 |
| 1320 3921 782 | 645226719 |
| 666013 964964 123456 | 556923723 |
 

h3. 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 .

== include(page="template/taskfooter" task_id="hagi") ==