Malnar 先生想把一张他自己的照片挂在墙上。墙可以表示为一个 $n$ 行 $m$ 列的矩阵。由于他以前多次在墙上挂过照片，一些位置上仍然嵌有钉子。这些位置用符号 "#" 标记，而空位用符号 "." 标记。
照片呈矩形，具有任意尺寸，挂在墙上时覆盖一个矩形区域。如果照片覆盖的区域内包含的钉子数量不超过一个，则照片可以挂在墙上。
请帮助 Malnar 先生计算他有多少种在墙上挂照片的方法。
输入格式
第一行包含 $n$ 和 $m$ ($1 \le n, m \le 500$)，表示墙的尺寸。
接下来的 $n$ 行，每行包含 $m$ 个字符 $c_{ij}$，描述墙面。每个字符要么是 "."，要么是 "#"（不含引号）。
输出格式
输出一行，表示在墙上挂照片的可能方法总数。
子任务
| 子任务 | 分值 | 数据范围 |
|---|---|---|
| 1 | 17 | $n, m \le 10$ |
| 2 | 21 | $n, m \le 100$ |
| 3 | 32 | 无额外限制 |
样例
输入格式 1
3 3 ... ... ..#
输出格式 1
36
说明
第一个样例的说明： 只要照片覆盖的钉子数量不超过一个，该放置方式就是有效的。
输入格式 2
4 4 .... .#.. #... #.#.
输出格式 2
76
说明
第二个样例的说明： 照片不能以同时覆盖位置 $(3, 1)$ 和 $(4, 1)$ 的方式放置。
输入格式 3
5 5 ..... #..#. ..#.# ..... ..#..
输出格式 3
154