== include(page="template/taskheader" task_id="teams2") ==

Liceul de Cultura General nr 2 din Dorohoi organizeaza un concurs pe echipe. Fiecare echipă trebuie să fie formată din K , 3 ≤ K ≤ 4 elevi din generaţii consecutive: un elev de clasa a IX-a (generaţia 0), unul de clasa a X-a (generaţia 1),  unul de clasă a XI-a (generaţia 2) si optional un elev de clasă a XII-a (generaţia 3), daca cel din urmă nu este ocupat cu bacaleaureatul. In mod curios, toate clasele liceului sunt formate din N elevi fiecare, 1 ≤ N ≤ 2000

Liceul de Cultura General nr 2 din Dorohoi organizeaza un concurs pe echipe. Fiecare echipa trebuie sa fie formata din K , 3 ≤ K ≤ 4 elevi din generatii consecutive: un elev de clasa a IX-a (generatia 0), unul de clasa a X-a (generatia 1),  unul de clasa a XI-a (generatia 2) si optional un elev de clasa a XII-a (generatia 3), daca cel din urma nu este ocupar cu bacaleaureatul. In mod curios, toate clasele liceului sunt formate din N elevi fiecare, 1 ≤ N ≤ 2000

Organizatorii concursului au masurat cu exactitate inteligenţa a fiecarui elev şi au observat ca nu există 2 elevi cu acelasi nivel de inteligenţă in intreaga şcoală. Fiecare elev a primit un ID cuprin intre 1 si N * k. Astfel, daca un copil a este mai inteligent decat un copil b, atuncti @ID(a)@ > @ID(b)@.Ei au mai observat ca niciun elev nu va vrea să fie in aceeasi echipă cu un elev mai inteligent dintr-o generatie mai tanară, deoarece se va simţi prost(la figurat). Organizatorii se intreabă in cate moduri se pot alege T echipe de K elevi, astfel incat fiecare elev al liceului să facă parte din maxim o echipă.

Organizatorii concursului au masurat cu exactitate inteligenta a fiecarui elev si au observat ca nu exista 2 elevi cu acelasi nivel dde inteligenta in intrega scoala. Fiecare elev a primit un If cuprin intre 1 si N * k. Astfel, daca un copil a este mai inteligent decat un copil b, atuncti ID(a) > ID(b).Ei au mai observat ca niciun elev nu va vrea sa fie in aceeasi echipa cu un elev mai inteligent dintr-o generatie mai tanara, deoarece se va simti prost(la figurat). Organizatorii se intreba in cate moduri se pot alege T echipe de K elevi, astfel incat fiecare elev al liceului sa faca parte din maxim o echipa.

Formal, fie K şiruri de N elemente ID[~0~], ID[~1~], ...,ID[~k-1~] , reprezentand Id-urile elevilor din cele K generatii, respectiv. Se cere să se numere in cate moduri se pot elege T echipe de forma (e[i,0],e[~i,1~],...., e[~i,K-1~]), 0 &le; e[~i,j~] &le; N-1 pentru orice 0 &le; i &le; T-1, 0 &l;e j &le; K-1. Toate echipele trebuie sa respecte proprietatea ID[~j,e[~i,j~]~] < ID[~j+1,e[~i,j+1~]~], pentru orice 0 &le; i &le; T-1 , 0 &le; j &le; K-2. In plus, niciun elev nu poate să apară in mai mult de o echipa. Doua modalitati de a alege echipele se considera distincte daca exista cel puţin o echipă care apare intr-o modalitate si nu apare in cealaltă.

Formal, fie K siruri de N elemente ID[~0~], ID[~1~], ...,ID[~k-1~] , reprezentand Id-urile elevilor din cele K generatii, respectiv. Se cere sa se numere in cate moduri se pot elege T echipi de forma (e[i,0],e[~i,1~],...., e[~i,K-1~]), 0 &le; e[~i,j~] &le; N-1 pentru orice 0 &le; i &le; T-1, 0 &l;e j &le; K-1. Toate echipele trebuie sa respecte proprietatea ID[~j,e[~i,j~]~] < ID[~j+1,e[~i,j+1~]~], pentru orice 0 &le; i &le; T-1 , 0 &le; j &le; K-2. In plus, niciun elev nu poate sa apara in mai mult de o echipa. Doua modalitati de a alege echipele se considera distincte daca exista cel putin o echipa care apare intr-o modalitate si nu apare in cealalta.

h2. Date de intrare

* linia 1: K N T, reprezentând numărul  de generaţii, numărul de elevi din fiecare generaţie, respectiv numărul de echipe care trebuie formate.
* linia 2 + i: ID[~i,0~] ID[~i,1~] ... ID[~i,N-1~], (0 ≤ i ≤ K-1)

Fişierul de intrare $teams2.in$ ...

h2. Date de ieşire

În fisierul de ieşire se va afla numarul de echipe ce se pot forma modulo  6 700 417
 
h2. Punctare
 
 
|_. Subtask |_. Punctaj |_. Constrangeri |
| 1         | 6 puncte  | 1 ≤ T ≤ N ≤ 5
                          K = 3                  |
| 2         | 6 puncte  | 1 ≤ T ≤ N ≤ 20
                          K = 3   |
| 3         | 31 puncte | 1 ≤ T ≤ B ≤ 40
                          K = 3 |
| 4         | 16 puncte | 1 ≤ T ≤ N ≤ 300
                          K = 3 |
| 5         | 16 puncte | 1 ≤ T ≤ 2000
                          K = 3 |
| 6         | 16 puncte | 1 ≤ T ≤ N ≤ 25
                          K = 4 |
| 7         | 9 puncte  | 1 ≤ T ≤ N ≤ 300
                          K = 4|
 
 

În fişierul de ieşire $teams2.out$ ...
h2. Restricţii
* $... ≤ ... ≤ ...$

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

|3 3 2
5 4 2
7 1 3
6 8 9
|8|
|4 3 1
2 1 4
3 7 5
11 6 10
9 8 12
|31|
|3 8 8
1 2 3 4 5 6 7 8
9 10 11 12 13 14 15 16
17 18 19 20 21 22 23 24
|4201486|
 
 

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

h3. Explicaţie

ID-urile elevilor din cele 8 solutii din primul exemplu sunt:
• (5, 7, 8) si (2, 3, 6)
• (5, 7, 8) si (2, 3, 9)
• (5, 7, 9) si (2, 3, 6)
• (5, 7, 9) si (2, 3, 8)
 
• (4, 7, 8) si (2, 3, 6)
• (4, 7, 8) si (2, 3, 9)
• (4, 7, 9) si (2, 3, 6)
• (4, 7, 9) si (2, 3, 8)

...

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