Symmetry

Time limit2sMemory limit1024 MB

Summary

Count the subgrids with an even number of columns that are mirror-symmetric across their vertical center line.

Level: Medium6 of 10
Topics: Matrix, String, Stack
Solved: No attempts yet

Problem

You are given an $N \times M$ grid $A$ . The cell in row $i$ and column $j$ contains an uppercase English letter $A_{i,j}$ .

A grid is called a symmetric grid if it satisfies all of the following conditions.

It has at least 1 row and an even number of columns, at least 2.
When the grid is folded along its exact vertical center line, every pair of characters that touch is the same.
- Specifically, for a grid $B$ of size $r \times 2c$ , $B_{i,j} = B_{i,2c+1-j}$ holds for all $(i, j)$ with $1 \le i \le r$ and $1 \le j \le c$ .

Count the subgrids of $A$ that are symmetric grids. A subgrid is formed by choosing consecutive rows and consecutive columns of $A$ .

Input

The first line contains two integers $N$ and $M$ , the number of rows and columns of $A$ , separated by a space. ( $2 \le N, M \le 500$ )

Each of the next $N$ lines contains $A_{i,1}, A_{i,2}, \cdots, A_{i,M}$ with no spaces. $A_{i,j}$ is the character in row $i$ , column $j$ of $A$ , and it is one of the uppercase English letters.

Output

Print the number of subgrids of $A$ that are symmetric grids.

Hint

This problem is not guaranteed to be solvable with Python3. If you use Python, submit with PyPy3. It has the same syntax as Python3 and usually runs faster.

Examples3

Example 1
Input
```
2 4
ABBA
CCCC
```
Expected output
```
8
```

Example 2

Input

6 8
AAAAAAAA
AABBAAAA
AAAAAAAA
AABBAAAA
AAAAAAAA
CAAAAAAC

Expected output

Example 3
Input
```
3 3
ABA
CDC
EFE
```
Expected output
```
0
```