You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

数子矩形

题目描述

有一个 $N \times M$ 的矩阵，这个矩阵里面有一些格子里有雷。 小明需要在这个矩阵中选出一个没有雷的矩形，很显然他有很多种选择的方案，但是他并不关心总的方案数，而是关心每个格子可以在多少种方案中被选中。

记 $f(i,j)$ 为 $(i,j)$ 这个格子在多少种方案中被选中，小明想问你 $\sum_{i=1}^N \sum_{j=1}^M f(i,j)$ 的值。

输入格式

第一行输入正整数 $N,M$，表示矩阵大小。

接下来的 $N$ 行，每行 $M$ 个字符。其中 . 表示该格没有雷，而 # 表示有雷。

输出格式

输出所求答案。不开long long见祖宗

样例 #1

样例输入 #1

2 3
.#.
#..

样例输出 #1

8

提示

样例解释1

下列矩阵代表 $f(i,j)$。所有 $f(i,j)$ 总和为 $8$。

1 0 2

0 2 3

数据范围

对于 $20\%$ 的数据，$1 \le N,M \le 10$。

对于 $50\%$ 的数据，$1 \le N,M \le 300$。

对于 $100\%$ 的数据，$1 \le N,M \le 2000$。