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$ 个字符，表示表格的初始状态。字符 “#” 表示已占用的格子，字符 “.” 表示未占用的格子。保证至少有两个未占用的格子，且初始状态下可以将所有未占用的格子用多米诺骨牌填满。

输出格式

设 $x$ 为 Dani 标记两个格子使得剩余未占用格子无法被多米诺骨牌完全填满的方法数。

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

样例

输入格式 1

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

输出格式 1

52

输入格式 2

2 2
..
..

输出格式 2

2

输入格式 3

2 2
#.
#.

输出格式 3

0