Cerința

Se dă o matrice binară de dimensiuni $n\times m$. Determinați numărul de cvadruplete $(r_1,r_2,c_1,c_2)$ care respectă următoarele condiții:

• $1\le r_1<r_2\le N$ și $1\le c_1<c_2\le M$.
• Celulele $(r_1,c_1)$ și $(r_1,c_2)$ conțin valoarea $1$.
• Celulele $(r_2,c_1)$, $(r_2,c_1+1)$, …, $(r_2,c_2)$ conțin toate valoarea $1$.

Date de intrare

Pe prima linie se vor afla valorile $n$ și $m$ (dimensiunile tablei). Următoarele $n$ linii descriu matricea. Fiecare va conține $m$ valori de $0$ sau $1$. A $c$-a valoare de pe a $r$-a dintre aceste linii reprezintă celula $(r,c)$.

Date de ieșire

Pe prima linie se va afișa numărul de cvadruplete care respectă condițiile.

Restricții și precizări

• Pentru toate testele, se respectă $1\le n\cdot m\le {10}^5$.
• Subtask 1, 20p: $n,m\le 40$
• Subtask 2, 30p: $n,m\le 100$
• Subtask 3, 20p: $n,m\le 300$
• Subtask 4, 30p: restricțiile inițiale

Exemplu 1:

Intrare

3 3
1 0 1
0 0 0
1 1 1

Ieșire

1

Explicație

Singurul cvadruplet este format din $r_1=1$, $r_2=3$, $c_1=1$ și $c_2=3$. Celulele $(1,1)$, $(1,3)$, $(3,1)$, $(3,2)$ și $(3,3)$ conțin toate valoarea $1$, deci condiția este respectată.

Exemplu 2:

Intrare

3 4
1 0 1 1
1 1 1 0
1 1 1 1

Ieșire

7

Explicație

Celulele de valoare $1$ din cele $7$ cvadruplete sunt reprezentate mai jos: