Description

Dora 喜欢玩多米诺骨牌。她拿来一个 $n \times m$ 的棋盘，将一些单元格标记为已占据，然后尝试用 $2 \times 1$ 的多米诺骨牌填满所有未被占据的单元格。

她的弟弟 Dani 喜欢对他姐姐搞恶作剧。所以当她不在的时候，他又将两个未被占据的单元格标记为已占据。他想通过这种方式，使得无法再用多米诺骨牌填满所有未被占据的单元格。

请帮助 Dani 计算他有多少种选择这两个单元格的方法。由于 Dani 最多数到一百万，如果方法数是 $x$，请输出 $\min(x, 10^6)$。

Input Format

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

Output Format

令 $x$ 为 Dani 标记两个单元格后，导致无法用多米诺骨牌填满所有未被占据的单元格的方法数。

输出一个整数 $\min(x, 10^6)$。

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

52

2 2
..
..

2

2 2
#.
#.

0

Hint

翻译由 gemini2.5pro 完成