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

table(example). |_. hagi.in |_. hagi.out |
| 2 2 1 | 6 |

| 1320 3921 782 | 191898394 |

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

-> 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") ==