Problem 1477: omogene

Se consideră o matrice cu $L$ linii și $C$ coloane care memorează doar valori din mulțimea $\{0, 1, 2\}$ . O submatrice nevidă (formată din cel puțin o linie și cel puțin o coloană) a acestei matrice o numim omogenă dacă numărul valorilor de $0$ este egal cu numărul de valori de $1$ și egal cu numărul valorilor de $2$ . De exemplu, în matricea

$\begin{array} {|r|r|r|r|r|r|r|r|r|} \hline 0 &1 &2 &0 \\ \hline 1 &2 &0 &1 \\ \hline \end{array}$

sunt șase submatrice omogene, acestea fiind:

$\begin{aligned} \text{1) } \begin{array} {|r|r|r|r|r|r|} \hline 0 &1 &2 \\ \hline 1 &2 &0 \\ \hline \end{array} & & \text{2) } \begin{array} {|r|r|r|r|r|r|} \hline 1 &2 &0 \\ \hline 2 &0 &1 \\ \hline \end{array} & & \text{3) } \begin{array} {|r|r|r|} \hline 0 &1 &2 \\ \hline \end{array} \end{aligned}$

$\begin{aligned} & \text{4) } \begin{array} {|r|r|r|} \hline 1 &2 &0 \\ \hline \end{array} & & \text{5) } \begin{array} {|r|r|r|} \hline 1 &2 &0 \\ \hline \end{array} & & \text{6) } \begin{array} {|r|r|r|} \hline 2 &0 &1 \\ \hline \end{array} \end{aligned}$

Submatricele a treia și a patra sunt formate din prima linie a matricei inițială, iar submatricele a cincea și a șasea sunt formate din a doua linie.

Cerință

Să se determine câte submatrice nevide omogene există.

Date de intrare

Fişierul omogene.in conţine pe prima linie numerele naturale $L$ și $C$ . Pe următoarele $L$ linii se află câte $C$ numere naturale separate prin spații reprezentând câte o linie din matrice.

Date de ieșire

Fişierul omogene.out va conţine pe prima linie un singur număr natural reprezentând numărul submatricelor nevide omogene.

Restricții și precizări

$2 \leq L \leq C \leq 5 \ 000$
$4 \leq L \cdot C \leq 65 \ 536$
Atenție, o submatrice este formată dintr-o secvență continuă de linii și coloane, deci, de exemplu, dacă se aleg dintr-o matrice liniile $1, 2$ și $5$ , atunci acestea nu formează o submatrice
Numărul submatricelor omogene va fi mai mic decât $2 \cdot 10^9$
Întreaga matrice poate fi submatrice omogenă

Exemplul 1

omogene.in

2 4
0 1 2 0
1 2 0 1

omogene.out

Explicație

Cele șase submatrice au fost menționate în enunț.

Exemplul 2