对于一个只包含 .
和 z
的矩阵,当以下条件满足时:
该矩阵的行数列数相等。
该矩阵的第一行与最后一行的字符全是
z
。该矩阵从右上角到左下角的对角线上的字符全是
z
。
我们称其为 Z
矩阵。
现在给定一个 $n \times m$ 的矩阵,请你计算它有多少个子矩阵是 Z
矩阵。
输入格式
第一行两个整数 $n$ , $m$ 分别表示矩阵的行数和列数 $(1 \leq n , m \leq 3 \times 10^3 )$。
接下来 $n$ 行, 每行包含 $m$ 个字符, 表示该矩阵。
输出格式
输出一行一个整数表示 Z
矩阵的数量。
样例输入
4 4
zzzz
z.z.
.zz.
zzzz
样例输出
14