题目背景

译自 COCI 2024/2025 #5 T2。$\texttt{1s,0.5G}$。满分为 $70$。

题目描述

有一面 $n$ 行 $m$ 列的矩形墙，被划分为 $n\times m$ 个区域。墙上有些区域有钉子，用 $\texttt{\#}$ 表示；其他的区域没有钉子，用 $\texttt{.}$。

现在要在墙上挂画。我们说一种挂画方式是合法的，当且仅当：

• 画占据墙上的一个矩形区域；
• 画占据的区域中至多一个区域存在钉子。

求出有多少种合法的挂画方式。

输入格式

第一行，两个正整数 $n,m$。

接下来 $n$ 行，第 $i$ 行一个字符串 $c$，$c_{i,j}$ 表示墙上第 $i$ 行第 $j$ 列的区域的状态。

输出格式

输出一行一个正整数表示答案。

3 3
...
...
..#

36

4 4
....
.#..
#...
#.#.

76

5 5
.....
#..#.
..#.#
.....
..#..

154

提示

样例解释

• 样例 $1$ 解释：随便怎么放都是合法的。

数据范围

对于 $100\%$ 的数据，保证 $1\le n\le 500$。