← 返回题目列表

Codeforces · 1773/D

D. 多米诺骨牌

中文机器翻译题面 查看原题

朵拉喜欢玩多米诺骨牌。她取出 $$$n \times m$$$ 表,将一些单元格标记为已占用,然后尝试用 $$$2 \times 1$$$ 多米诺骨牌填充所有未占用的单元格。

她的弟弟丹尼喜欢对他的姐姐恶作剧。因此,当她离开时,他会将另外两个未占用的牢房标记为已占用。他希望以这样一种方式来实现,即不可能用多米诺骨牌填满所有未占用的单元。

帮助 Dani 数一下他可以选择这两个单元格的方式数量。由于Dani只能数到一百万,如果这个路数是$$$x$$$,则输出$$$\min(x, 10^6)$$$。

输入

第一行包含整数 $$$n$$$ 和 $$$m$$$ ($$$1\le n, m\le 1000$$$)。接下来的 $$$n$$$ 行每行包含 $$$m$$$ 个字符——表的初始状态。字符“#“对应于已占用的单元格,并且字符”.”对应于未占用的单元格。保证至少有两个未被占用的单元格,并且有可能用多米诺骨牌填满所有未被占用的单元格。

输出

设 $$$x$$$ 为 Dani 标记两个单元格的方式数量,使得不可能用多米诺骨牌填充所有未占用的单元格。

打印一个整数$$$\min(x, 10^6)$$$。

示例

输入
复制

3 6
...#..
......
#...##

输出
复制

52

输入
复制

2 2
..
..

输出
复制

2

输入
复制

2 2
#.
#.

输出
复制

0