旋转木马精品店又忙了!瑞瑞决定去参加小马舞会,她肯定需要一件新衣服,因为多次穿着同一件衣服出去是不礼貌的表现。首先,她需要一个礼服图案,她将从一块长方形的彩色布料上剪下该图案。
这块彩色织物由 $$$n \times m$$$ 单独的方形碎片组成。由于瑞瑞喜欢款式新颖的连衣裙,因此连衣裙图案只能包含颜色相同的碎片。连衣裙图案必须是正方形,而且由于瑞瑞喜欢菱形,图案的边必须与一块布料的边形成 $$$45^{\circ}$$$ 角(这样就会类似于传统的菱形图片)。
正确着装图案示例: 不正确着装图案示例:第一个由多种颜色的碎片组成,第二个超出了布料的范围,第三个不是边与布料的边形成 $$$45^{\circ}$$$ 角度的正方形。
瑞瑞想知道有多少种方法可以剪出满足所有现有条件的服装图案。请帮助她并满足她的好奇心,以便她能够继续创作她的新杰作!
输入
第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n, m \le 2000$$$)。接下来的 $$$n$$$ 行中的每一行都包含 $$$m$$$ 字符:小写英文字母,其中第 $$$j$$$ 对应于当前行和第 $$$j$$$ 列中的废料。具有相同字母的剪贴画具有相同的颜色,具有不同字母的剪贴画具有不同的颜色。
输出
打印一个整数:满足瑞瑞所有条件的剪裁服装图案的方法数。
示例
输入 #1
3 3 aaa aaa aaa
输出 #1
10
输入 #2
3 4 abab baba abab
输出 #2
12
输入 #3
5 5 zbacg baaac aaaaa eaaad weadd
输出 #3
31
注意
在第一个示例中,所有尺寸为 $$$1$$$ 的连衣裙图案和一个尺寸为 $$$2$$$ 的连衣裙图案均令人满意。
在第二个示例中,只有尺寸为 $$$1$$$ 的连衣裙图案令人满意。