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 \cdot M$ unde pentru toate perechile $(i,j)$ valoarea $C_{ij}$ 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?

Cerinţă

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.

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.

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 $1 \ 000 \ 000 \ 007$ al numărului de perechi de şiruri pentru care matricea $C$ reprezintă un entanglement.

Restricții și precizări

• $1 \leq N, M \leq 300$
• $1 \leq K \leq N \cdot M$
• Pentru teste în valoare de $32$ de puncte $T = 1$.
• Pentru teste în valoare de $32$ de puncte $T = 2$ şi $N, M \leq 60$.
• Pentru restul testelor, în valoare de $36$ de puncte, $T = 2$.

Exemplul 1

entanglement.in

1 2 2 2
1 1
1 2

entanglement.out

DA

Explicație

O posibilă soluţie este $A$ = {$1, 1$} şi $B$ = {$1, 2$}.

Exemplul 2

entanglement.in

2 2 2 2
1 1
1 2

entanglement.out

5

Explicație

Cele $5$ soluţii sunt:
$(A = \{1, 1\}, B = \{1, 2\})$
$(A = \{1, 1\}, B = \{2, 2\})$
$(A = \{1, 2\}, B = \{1, 1\})$
$(A = \{2, 2\}, B = \{1, 1\})$
$(A = \{1, 2\}, B = \{1, 2\})$