407935: GYM102946 B Bongcloud

Bob the shark enjoys playing chess. In fact, he has just won the Legendary Grandmaster title.

The sharks do not play chess on a regular chessboard, because they think that's boring. Instead, they have a board with $$$n$$$ rows and $$$m$$$ columns, where each square is either black or white. For each game of chess, they pick a region on the board as the "play region" of the game. The play region should be a rectangle of positive area, with each side parallel to one of the board's sides, and each vertex at the corner of some square on the board. Two regions are the same if they contain the same set of squares on the board, otherwise they are different.

An example of a board with 4 rows and 5 columns. The red rectangle on the right marks a possible play region containing 9 squares.

Bob's favorite chess move is the "Bongcloud Attack". He uses this move in chess tournaments very often, because it is always a powerful surprise attack that no opponent would expect. One day, he played the Bongcloud as usual, and the opponent took very long to think about the next move. While the opponent was still thinking, the following question came to Bob's mind: How many different play regions on the board are vertically symmetric? A region is called vertically symmetric if it looks the same after reversing its rows. For example, the region shown above is vertically symmetric. Please help Bob calculate the answer with a program.

The first line contains two integers $$$n$$$ and $$$m$$$.

The following $$$n$$$ lines describe the sharks' board. Each line contains $$$m$$$ characters. The $$$j$$$-th character on the $$$i$$$-th line denotes the color of the square at the $$$i$$$-th row, $$$j$$$-th column: 1 for a white square, or 0 for a black square.

Technical specification:

• $$$1 \le n, m$$$
• $$$n \times m \le 10^6$$$

Print one integer, the answer to Bob's question.

2 2
01
00

7

3 4
0101
0100
0001

42