G-Beautiful Matrix_2026牛客五一集训派对day1

时间限制：C/C++/Rust/Pascal 5秒，其他语言10秒
空间限制：C/C++/Rust/Pascal 1024 M，其他语言2048 M
Special Judge, 64bit IO Format: %lld

题目描述

You are given a character matrix $s$ of size $n\times m$ .

Let’s call a $n\times m$ matrix $s$ beautiful if and only if $n=m$ and $\forall i, j\in[1,n], s_{i,j}=s_{n-i+1,n-j+1}$ .

Let’s call a matrix’s beauty the number of beautiful submatrices in it.

Your task is to calculate the beauty of the given character matrix.

A submatrix of a matrix is formed by selecting some contiguous rows and columns in the matrix and forming a new matrix by using those entries in the same relative positions.

Please pay attention to the the time complexity of the program.

输入描述:

The first line contains two integers $n$ and $m$ ( $1\le n,m\le 2000$ ) — the size of the given matrix.

Then there are $n$ lines, each line contains a string of lowercase English characters with length $m$ — the matrix.

输出描述:

Output a single integer — the beauty of the given matrix.

示例1

输入

复制

3 4
abcz
dedz
cbaz

输出

复制