题目描述

译自 COCI 2018/2019 Contest #1 T4「Strah」

对于 Mirko 来说，他最害怕的事情就是找位置种草莓。Mirko 有 $N \times M$ 块田地，有的位置适合种草莓而有的不适合，因为有杂草。一个合适矩形是指这个矩形中的每一块田地都是适合种草莓的。Mirko 对每一块田地的潜力值很感兴趣。一块田地的潜力值是有多少个合适矩形覆盖它。

请你帮助 Mirko 算出所有田地潜力值的和。

输入格式

第一行输入两个正整数 $N, M$。

接下来 $N$ 行，每行一个长为 $M$ 的字符串，只由 . 和 # 组成，. 表示这块田地适合种草莓，# 表示这块田地不适合。

输出格式

一行输出一个整数，表示所有田地的潜力值之和。

2 3
.#.
..#

8

3 3
...
...
...

100

3 4
..#.
#...
...#

40

数据范围与提示

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

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

对于 $100\%$ 的数据，保证 $1\le N, M \le 2 \times 10^3$。