在执政党“A”部长帕维尔的一次会议上建议改善下水道系统并在该市建造一条新管道。
城市是一个 n × m 的矩形区域。该区域的每个方格要么是空的(然后管道可以进入其中),要么是被占用的(管道不能进入该方格)。空方格由字符“.”表示,已占用方格由字符“#”表示。
管道必须满足以下标准:
- 管道是宽度为 1 的折线,
- 管道进入空方块,
- 管道从场地边缘开始,但不是从角落方块开始,
- 管道终止于场地边缘,但不在角落广场,
- 管道最多有 2 圈(90 度),
- 字段的边框方块必须与管道正好共享两个方块,
- 如果管道看起来像一个单段,则管道的端点必须位于场地的不同边缘上,
- 对于管道的每个非边界方块,恰好有两个边相邻的方块也属于管道,
- 对于管道的每个边框方块,恰好有一个也属于管道的侧相邻单元格。
以下是允许的管道路线的一些示例:
以下是禁止管道路线的一些示例:
在这些示例中,管道由字符“*”表示。
你被要求编写一个程序来计算在城市中制作一根管道的不同方法的数量。
如果两种制作管道的方法至少在一个正方形中不同,则认为它们是不同的。
输入
输入的第一行包含两个整数 n, m (2 ≤ n, m ≤ 2000) — Berland 地图的高度和宽度。
接下来的 n 行每行包含 m 个字符——城市地图。
如果地图上的方块用字符“.”标记,则该方块是空的,管道可以穿过它。
如果地图上的方格被字符“#”标记,则该方格已满,管道无法通过。
输出
在输出的第一行中打印一个整数 - 创建管道的不同方法的数量。
示例
输入 #1
3 3 ... ..# ...
输出 #1
3
输入 #2
4 2 .. .. .. ..
输出 #2
2
输入 #3
4 5 #...# #...# ###.# ###.#
输出 #3
4
注意
在第一个示例中,有 3 种制作管道的方法(管道的方块用字符“*”标记):