8996: Beautiful Matrix

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 ∀i,j∈[1,n],si,j=sn−i+1,n−j+1\forall i, j\in[1,n], s_{i,j}=s_{n-i+1,n-j+1}∀i,j∈[1,n],si,j=sn−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.