mexitate

Se dă o matrice $A$ cu $N$ linii şi $M$ coloane cu elemente numere naturale nu neapărat distincte. Pentru o submatrice definim $MEX$-ul acesteia ca fiind cea mai mică valoare naturală nenulă care nu apare în aceasta.

Cerință

Să se calculeze produsul $MEX$-urilor tuturor submatricelor având $K$ linii şi $L$ coloane ale matricei $A$.

Date de intrare

Pe prima linie a fișierului de intrare mexitate.in se găsesc patru numere naturale $N$, $M$, $K$ si $L$ separate printr-un spaţiu cu semnificaţia din enunţ. Pe fiecare dintre următoarele $N$ linii se află câte $M$ numere naturale nenule, despărţite prin câte un spaţiu, reprezentând valorile matricei.

Date de ieșire

În fișierului de ieșire mexitate.out se va găsi un singur număr natural reprezentând produsul $MEX$-urilor tuturor submatricelor având $K$ linii şi $L$ coloane ale matricei, modulo $10^9+7$.

Restricții și precizări

• $1 \leq N \cdot M \leq 400 \ 000$
• $1 \leq K \leq N$
• $1 \leq L \leq M$
• Fiecare element al matricei are valoarea între $1$ și $N \cdot M$.
• Pentru 20 de puncte există teste cu $1 \leq N, M \leq 50$.
• Pentru alte 20 de puncte există teste cu $1 \leq N, M \leq 630$.

Exemplu

mexitate.in

3 4 2 3
1 2 3 2
2 3 1 4
1 1 2 6

mexitate.out

400

Explicație

$N = 3$ şi $M = 4$
$K = 2$ şi $L = 3$

Submatricile cu $2$ linii şi $3$ coloane sunt:

• $\begin{pmatrix} 1 & 2 & 3 \\ 2 & 3 & 1 \end{pmatrix}$ cu $MEX = 4$;
• $\begin{pmatrix} 2 & 3 & 2 \\ 3 & 1 & 4 \end{pmatrix}$ cu $MEX = 5$;
• $\begin{pmatrix} 2 & 3 & 1 \\ 1 & 1 & 2 \end{pmatrix}$ cu $MEX = 4$;
• $\begin{pmatrix} 3 & 1 & 4 \\ 1 & 2 & 6 \end{pmatrix}$ cu $MEX = 5$.

Produsul tuturor $MEX$-urilor este $4 \cdot 5 \cdot 4 \cdot 5 = 400$.
$400\ \%\ 1 \ 000 \ 000 \ 007 = 400$.