题目描述

现在有一个 n × m n×m 的网格, 网格的每一个位置有一个颜色。

现在你需要统计有多少个子矩形，满足：

1.这个子矩形由自上而下三条横向的颜色带组成

2.每一条颜色带宽度相等

3.相邻两个颜色带颜色不能相同。

如上是合法矩阵

如上是不合法矩阵

输入格式

第一行两个整数 n,m，表示矩形长宽。

接下来 n 行，每行一串长 m 的小写字母字符串，表示矩形第 i 行从左到右的颜色。

输出格式 一行一个整数，表示合法子矩形个数。

样例

样例输入;
4 3
aaa
bbb
ccb
ddd

样例输出：
6

对于 10% 数据，有 n , m ≤ 20

对于 20% 数据，有 n , m ≤ 40

对于 30% 数据，有 n , m ≤ 100

对于 50% 数据，有 n , m ≤ 500

对于 70% 数据，有 n , m ≤ 1500

对于 100% 数据，有 1 ≤ n , m ≤ 6000 ，保证仅使用不同的小写字母表示不同的颜色。