Background

The full score for this problem is $110$.

Problem Description

The frog Maša is playing in a lake consisting of $n$ rows and $m$ columns. Each cell of the lake is either the character $0$ (meaning water) or $1$ (meaning a lily pad).

Maša can only stand on lily pads. From one lily pad, she can jump to any other lily pad in the same row or the same column. However, her jumps must alternate: if the previous jump changed the column, then the next jump must change the row. If the previous jump changed the row, then the next jump must change the column.

Each time Maša jumps away from her current lily pad, that lily pad sinks and cannot be jumped onto again.

Maša wants to visit a total of $5$ lily pads in one path (including the starting pad). She may choose any lily pad as the starting point. Compute how many paths satisfy the conditions. Two paths are considered different if the coordinates of the lily pads at any of positions $1 \sim 5$ are different.

Input Format

The first line contains two natural numbers $n, m$ ($1 \le n, m \le 2000$).

The next $n$ lines each contain $m$ characters ($0$ or $1$), describing the lake grid.

Output Format

Output a single integer, the number of paths that satisfy the conditions.

2 3
111
110

4

4 4
1111
1111
1111
1111

2304

2 5
11110
01111

48

Hint

Sample Explanation

Explanation for Sample #1:

The $4$ paths are:

• $(1,1)\to(2,1)\to(2,2)\to(1,2)\to(1,3)$
• $(1,2)\to(2,2)\to(2,1)\to(1,1)\to(1,3)$
• $(1,3)\to(1,2)\to(2,2)\to(2,1)\to(1,1)$
• $(1,3)\to(1,1)\to(2,1)\to(2,2)\to(1,2)$

Subtasks

Translated by ChatGPT 5