== include(page="template/taskheader" task_id="entanglement") ==
Fie două şiruri A şi B de lungimi N şi M cu numere naturale mai mici sau egale decât K. Un entanglement al celor două şiruri este o matrice C de dimensiuni N x M unde pentru toate perechile (i,j)valoarea C[i][j] este egală fie cu A[i] fie cu B[j].
Dându-se o matrice C, câte perechi de şiruri (A,B) există pentru care C este un entanglement al celor două şiruri?
Fie două şiruri $A$ şi $B$ de lungimi $N$ şi $M$ cu numere naturale mai mici sau egale decât $K$. Un entanglement al celor două şiruri este o matrice $C$ de dimensiuni $N x M$ unde pentru toate perechile $(i,j)$ valoarea $C[i][j]$ este egală fie cu $A[i]$ fie cu $B[j]$.
Dându-se o matrice $C$, câte perechi de şiruri $(A,B)$ există pentru care $C$ este un entanglement al celor două şiruri?
h2. Cerinţă
Să se scrie un program care, pentru N, M, K şi matricea C cunoscute, determină:
Să se scrie un program care, pentru $N, M, K$ şi matricea $C$ cunoscute, determină:
* dacă matricea C poate fi un entanglement a două şiruri;
* numărul de perechi de şiruri (A,B) pentru care matricea C reprezintă un entanglement.
* dacă matricea $C$ poate fi un entanglement a două şiruri;
* numărul de perechi de şiruri $(A,B)$ pentru care matricea $C$ reprezintă un entanglement.
h2. Date de intrare
Fişierul de intrare entanglement.in conţine pe prima linie numerele T, N, M şi K, iar pe următoarele N linii câte M numere naturale reprezentând elementele din matricea C.
Dacă T=1 atunci se va stabili dacă matricea C poate fi un entanglement, iar dacă T=2 atunci se va determina numărul de perechi de şiruri (A,B) pentru care C reprezintă un entanglement.
Fişierul de intrare $entanglement.in$ conţine pe prima linie numerele $T, N, M$ şi $K$, iar pe următoarele $N$ linii câte $M$ numere naturale reprezentând elementele din matricea $C$.
Dacă $T=1$ atunci se va stabili dacă matricea $C$ poate fi un entanglement, iar dacă $T=2$ atunci se va determina numărul de perechi de şiruri $(A,B)$ pentru care $C$ reprezintă un entanglement.
h2. Date de ieşire
Dacă T=1 fişierul de ieşire entanglement.out va conţine cuvântul “DA” dacă C poate fi un entanglement sau cuvântul “NU” în caz contrar.
Dacă T=2 fişierul de ieşire entanglement.out va conţine un singur număr reprezentând restul modulo 1000000007 al numărului de perechi de şiruri pentru care matricea C reprezintă un entanglement.
Dacă $T=1$ fişierul de ieşire $entanglement.out$ va conţine cuvântul $“DA”$ dacă $C$ poate fi un entanglement sau cuvântul $“NU”$ în caz contrar.
Dacă $T=2$ fişierul de ieşire $entanglement.out$ va conţine un singur număr reprezentând restul $modulo 1000000007$ al numărului de perechi de şiruri pentru care matricea C reprezintă un entanglement.
h2. Restricţii
* 1 ≤ N, M ≤ 300
* 1 ≤ K ≤ N * M
* Pentru teste în valoare de 32 de puncte T = 1.
* Pentru teste în valoare de 32 de puncte T = 2 şi N, M <= 60.
* Pentru restul testelor, în valoare de 36 de puncte, T = 2.
* $1 ≤ N, M ≤ 300$
* $1 ≤ K ≤ N * M$
* Pentru teste în valoare de $32$ de puncte $T = 1$.
* Pentru teste în valoare de $32$ de puncte $T = 2$ şi $N, M <= 60$.
* Pentru restul testelor, în valoare de $36$ de puncte, $T = 2$.
h2. Exemplu
