teams

Cerință

Liceul de Cultură Generală nr. $2$ din Dorohoi organizează un concurs pe echipe. Fiecare echipă trebuie să fie formată din $K$, $3 \leq K \leq 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 clasa a XI-a (generaţia $2$) si opțional un elev de clasa 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 \leq N \leq 2 \ 000$.

Organizatorii concursului au măsurat cu exactitate inteligenţa fiecărui elev şi au observat că nu există $2$ elevi cu același nivel de inteligenţă în întreaga şcoală. Fiecare elev a primit un ID cuprins între $1$ și $N \cdot k$. Astfel, dacă un copil $a$ este mai inteligent decât un copil $b$, atunci $ID(a) > ID(b)$. Ei au mai observat că niciun elev nu va vrea să fie in aceeași echipă cu un elev mai inteligent dintr-o generatie mai tânără, deoarece se va simţi prost(la figurat). Organizatorii se întreabă în câte moduri se pot alege $T$ echipe de $K$ elevi, astfel încât fiecare elev al liceului să facă parte din maxim o echipă.

Formal, fie $K$ şiruri de $N$ elemente $ID_0, ID_1, \dots, ID_{k-1}$ , reprezentând Id-urile elevilor din cele $K$ generații, respectiv. Se cere să se numere în câte moduri se pot alege $T$ echipe de forma $(e_{i,0}, e_{i,1}, \dots, e_{i,K-1})$, $0 \leq e_{i,j} \leq N-1$ pentru orice $0 \leq i \leq T-1$, $0 \leq j \leq K-1$. Toate echipele trebuie să respecte proprietatea $ID_{j, e_{i,j}} < ID_{j+1, e_{i,j+1}}$, pentru orice $0 \leq i \leq T-1$, $0 \leq j \leq K-2$. În plus, niciun elev nu poate să apară in mai mult de o echipă. Două modalitati de a alege echipele se consideră distincte daca există cel puţin o echipă care apare într-o modalitate și nu apare în cealaltă.

Date de intrare

Fișierul de intrare teams.in are urmatoarea structură:

• 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} \dots ID_{i,N-1}$, $(0 \leq i \leq K-1)$

Date de ieșire

Pe prima linie a fișierului de ieșire teams.out se va găsi un singur număr întreg, numărul de echipe ce se pot forma modulo $6 \ 700 \ 417$

Restricții și precizări

• $3 \leq K \leq 4$;
• $1 \leq T, N \leq 2 \ 000$;

Exemplul 1

teams.in

3 3 2
5 4 2
7 1 3
6 8 9

teams.out

8

Explicație

ID-urile elevilor din cele $8$ soluții 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)$

Exemplul 2

teams.in

4 3 1
2 1 4
3 7 5
11 6 10
9 8 12

teams.out

31

Exemplul 3

teams.in

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

teams.out

4201486