CF1773D Dominoes

Dora喜欢玩多米诺骨牌。玩法是在一个 $n×m$ 的表格中标记一些格子，然后用 $2×1$ 的多米诺骨牌填满其他空格子。注意，多米诺骨牌不能放在标记过的格子上。 Dora的弟弟Dani喜欢搞恶作剧，趁Dora不在时，他会在表格中又标记两个格子。请告诉他有多少种标记的方案，使多米诺骨牌无法填充到所有空格子里。 但是Dani只能数到 $10^6$。如果方案数超过 $10^6$，请输出 $10^6$。

一共 $n+1$ 行。 第一行，两个整数 $n$ 和 $m$ ( $1≤n,m ≤1000$ )。 下面 $n$ 行，每行 $m$ 个字符。字符“#”表示一个被标记的格子，字符“.”表示一个空格子。保证至少有两个空格子，并且可以用多米诺骨牌将所有空格子填满。

一行，一个整数，为方案数与 $10^6$ 取最小值。