5900 - 状压DP:轮廓线DP:闭合回路(模板题)

通过次数

2

提交次数

2

时间限制 : 1 秒
内存限制 : 128 MB

给出 n\times m 的方格,有些格子不能铺线,其它格子必须铺,形成一个闭合回路。问有多少种铺法?

输入

第一行,两个整数,分别代表 n,m

从第二行到第 (n+1) 行,每行有一个长度为 m 的只含 *. 的字符串,* 表不能铺线,. 表必须铺。

输出

输出一行一个整数,表示总方案数。

样例

输入

4 4
**..
....
....
....

输出

2

输入

4 4
....
....
....
....

输出

6

提示

数据规模与约定

  • 对于 100\% 的数据,保证 2\le n,m\le 12