背景

多拉喜欢用多米诺骨牌玩游戏。她拿出一个$n \times m$的桌面，将一些单元格标记为已占用，然后尝试用$2 \times 1$的多米诺骨牌填满所有未占用的单元格。

她的小弟弟丹尼喜欢捉弄他的姐姐。所以，当她离开时，他将两个未占用的单元格标记为已占用。他想要这样做，以至于不可能再用多米诺骨牌填满所有的未占用单元格。

帮助丹尼计算他可以选择这两个单元格的方式数量。由于丹尼只能数到一百万，如果该数量为$x$，则输出$\min(x, 10^6)$。

描述

输入

第一行包含两个整数$n$和$m$，表示桌面的尺寸$(1 \leq n, m \leq 1000)$。接下来的$n$行每行包含$m$个字符——桌面的初始状态。字符#表示一个已占用的单元格，字符.表示一个未占用的单元格。保证至少有两个未占用的单元格，并且有可能用多米诺骨牌填满所有未占用的单元格。

输出

令$x$为丹尼将两个单元格标记为已占用，使得无法用多米诺骨牌填满所有未占用单元格的方式数量。

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

示例

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

52

2 2
..
..

2

2 2
#.
#.

0