Fie o matrice cu L linii și C coloane care memorează numere naturale. O submatrice a sa având colțul stânga-sus (xs, ys) și colțul dreapta-jos (xd, yd) este formată din toate elementele din matrice având indicele liniei în intervalul [xs, xd] și indicele coloanei în intervalul [ys, yd]. O submatrice poate fi formată dintr-un singur element.

Cerința

Scrieți un program care determină numărul submatricelor care au suma elementelor divizibilă cu 3.

Date de intrare

Fișierul de intrare matd3.in conține pe prima linie numerele naturale L și C separate prin spațiu. Pe următoarele L linii se află câte C numere naturale separate prin câte un spațiu reprezentând câte o linie din matrice.

Date de ieșire

Fișierul de ieșire matd3.out va conține pe prima linie un singur număr natural K, reprezentând numărul submatricelor care au suma divizibilă cu 3.

Restricții și precizări

• 2 ≤ L, C ≤ 300
• elementele matricei sunt numere naturale cuprinse între 0 și 10.000
• pentru toate testele, rezultatul va fi mai mic decât 2.000.000.000
• numărul 0 este divizibil cu 3

Exemplu:

matd3.in

2 3
1 2 2
2 1 3

matd3.out

7

Explicație

Cele șapte submatrice sunt:

\begin{pmatrix}
1&2\\
\end{pmatrix}

\begin{pmatrix}
2&1\\
\end{pmatrix}

\begin{pmatrix}
2&1&3\\
\end{pmatrix}

\begin{pmatrix}
3\\
\end{pmatrix}

\begin{pmatrix}
1\\
2\\
\end{pmatrix}

\begin{pmatrix}
2\\
1\\
\end{pmatrix}

\begin{pmatrix}
1&2\\
2&1\\
\end{pmatrix}