8996: Beautiful Matrix

内存限制:128 MB 时间限制:1 S
题面:传统 评测方式:文本比较 上传者:
提交:0 通过:0

题目描述

You are given a character matrix sss of size n×mn\times mn×m.
Let’s call a n×mn\times mn×m matrix sss beautiful if and only if n=mn=mn=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=sni+1,nj+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 nnn and mmm (1≤n,m≤20001\le n,m\le 20001n,m2000) — the size of the given matrix.
Then there are nnn lines, each line contains a string of lowercase English characters with length mmm — the matrix.

输出格式



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


输入样例 复制

3 4
abcz
dedz
cbaz

输出样例 复制

13