题目描述

师父给了你一个 $n$ 行 $m$ 列的矩阵 $a_{n\times m}$，矩阵中只包含小写英文字母 a 至 z，紧接着她给你出了这样一道难题。

使用左上顶点与右下顶点的坐标来描述一个子矩阵的位置，设两个坐标分别为 $(x_1,y_1)$ 与 $(x_2,y_2)$，称一个子矩阵是好的，当且仅当以下两个条件均满足：

• $1\le x_1<x_2\le n$，$1\le y_1<y_2\le m$。
• 这个矩阵边界上的所有字符全部相同。其中，定义一个矩形的边界为集合 $\{a_{x_1,j}|y_1\le j\le y_2\}\cup\{a_{x_2,j}|y_1\le j\le y_2\}\cup\{a_{i,y_1}|x_1\le i\le x_2\}\cup\{a_{i,y_2}|x_1\le i\le x_2\}$。

现在师父要求你快速求出好的子矩阵的个数，请你完成这道试炼吧。

输入格式

从文件 star.in 中读入数据。

第一行包含两个正整数 $n,m$。

接下来 $n$ 行，每行包含一个长度为 $m$ 的字符串，表示矩阵的每一行。

输出格式

输出到文件 star.out 中。

输出一行一个整数，表示答案。

样例1输入

3 4
aaaa
aaba
aaaa

样例1输出

5

样例2输入

5 6
aaaaaa
abaaca
aaaaaa
aazzaa
aazzaa

样例2输出

15

样例3

见题目目录下的 3.in 与 3.ans。

样例3解释

这个数据满足 Subtask 2 的限制。

样例4

见题目目录下的 4.in 与 4.ans。

样例4解释

这个数据满足 Subtask 4 的限制。

子任务

本题存在子任务捆绑

对所有数据，保证 $1\le n,m\le 3000$，矩阵中只包含小写英文字母 a 至 z。

​