朵拉喜欢玩多米诺骨牌。她取出 $$$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