Problem Description

While traveling, Xiao Lan saw a stone at a scenic spot. This stone carries a legend.

The legend says that long ago, a couple were separated during wartime. After enduring many hardships, they reunited several years later. To commemorate this experience, they left two engraved marks on a stone. Each mark is a line segment that is horizontal or vertical to the ground (note that a mark may have length $1$), and the length of a mark is a positive integer.

After many years of weathering, the stone has become uneven, and it is no longer possible to determine the positions of the two marks. However, Xiao Lan learned from the tour guide that the two marks from that year did not intersect: the two segments have no common point (including endpoints).

Xiao Lan now wants to know how many different possibilities there are for the positions of the two marks. In particular:

• When the mark length is $1$, horizontal and vertical directions are not distinguished. A mark at the same position $(x, y)$ counts as only $1$ possibility.
• Different orders of the two marks are considered different possibilities (for example, mark A first and mark B second is considered different from mark B first and mark A second).

In this problem, the stone is represented by an $n \times m$ $01$ matrix. If a position is $0$, it means it cannot be occupied by a mark; if it is $1$, it means it may be occupied by a mark. A mark corresponds to a horizontal or vertical line segment of width $1$ in the matrix, and all corresponding positions in the matrix must be $1$:

• For a horizontal mark, in the same row, all values in the matrix from the start point to the end point (including endpoints) are $1$.
• For a vertical mark, in the same column, all values in the matrix from the start point to the end point (including endpoints) are $1$.

Input Format

The first line contains two positive integers $n, m$, separated by a space, representing the size of the stone.

The next $n$ lines each contain a $01$ string of length $m$.

Output Format

Output one line containing an integer, representing the answer: how many different possibilities there are for the positions of the two marks.

1 2
11

2

2 2
11
11

32

Hint

Sample Explanation 1

There are two possibilities in total.

The first possibility: the first mark occupies row $1$, column $1$, with length $1$, and it is impossible to tell whether it is horizontal or vertical. The second mark occupies row $1$, column $2$, with length $1$, and it is impossible to tell whether it is horizontal or vertical.

The second possibility: the first mark occupies row $1$, column $2$, with length $1$, and it is impossible to tell whether it is horizontal or vertical. The second mark occupies row $1$, column $1$, with length $1$, and it is impossible to tell whether it is horizontal or vertical.

Constraints

For $30\%$ of the testdata, $n, m \le 50$.

For $60\%$ of the testdata, $n, m \le 300$.

For all testdata, $1 \le n, m \le 3000$.

Translated by ChatGPT 5