Bảng đẹp

Một bảng số nguyên không âm được gọi là bảng đẹp nếu tổng các số trong bảng chia hết cho \(9\).

Ví dụ, bảng
\(\begin{bmatrix} 3 & 3 & 3\\ 1 & 2 & 6 \end{bmatrix}\)
là một bảng đẹp.

Yêu cầu: Cho bảng số nguyên không âm kích thước \(m × n\), hãy đếm số bộ chỉ số \((x,y,u,v)\) với \(1 \leq x \leq u \leq m;1 \leq y\leq v \leq n\) sao cho bảng số con có ô trái trên \((x,y)\) và ô phải dưới \((u,v)\) là một bảng đẹp.

Input

• Dòng đầu chứa số nguyên \(m, n\)

• Dòng thứ \(i\) \((1 \leq i \leq m)\) trong \(m\) dòng sau chứa \(n\) số nguyên \(a_{(i,1)},a_{(i,2)},..,a_{(i,n)}\) \((a_{(i,j)} \leq 10^9)\).

Output

• In ra một số nguyên là số bộ chỉ số \((x,y,u,v)\) thỏa mãn.

Example

2 3
3 3 3
1 2 6

5

Scoring

• Subtask #1 (\(30\%\) số điểm): \(m, n \leq 5\)

• Subtask #2 (\(40\%\) số điểm): \(m, n \leq 50\)

• Subtask #3 (\(30\%\) số điểm): \(m, n \leq 500\)