P12793 [NERC 2022] Dominoes

Dora 喜欢玩多米诺骨牌。她拿来一个 $n \times m$ 的棋盘，将一些单元格标记为已占据，然后尝试用 $2 \times 1$ 的多米诺骨牌填满所有未被占据的单元格。  她的弟弟 Dani 喜欢对他姐姐搞恶作剧。所以当她不在的时候，他又将两个未被占据的单元格标记为已占据。他想通过这种方式，使得无法再用多米诺骨牌填满所有未被占据的单元格。 请帮助 Dani 计算他有多少种选择这两个单元格的方法。由于 Dani 最多数到一百万，如果方法数是 $x$，请输出 $\min(x, 10^6)$。

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

令 $x$ 为 Dani 标记两个单元格后，导致无法用多米诺骨牌填满所有未被占据的单元格的方法数。 输出一个整数 $\min(x, 10^6)$。

翻译由 gemini2.5pro 完成