3125 - CITY

小明和小华要参加NOI，踏上了去X市的火车。 小明望着窗外的田野，大楼，工厂缓缓后退，在思考着什么。 这时，对面的小华拿出手机对着他说：“看！我们在这个位置！” 小明望着手机上显示的地图，城市被接到分割成各个方块，而自己所在的点在慢慢移动。 他突然意识到自己甚至还没游历过这个自己所在的小城市，学校和家貌以及之间来回的道路似乎成了这个小城的唯一印象。 若我把它们全部走一圈，可能要仔细计划下吧……不，那么多方案，其实我应该早能做到了吧……小明在心里对自己说。

输入

第一行有两个数N, M表示地图被分割成N*M个块，接下来有N行，每行有M个字符。 . 表示这个块可以通过

  • 表示这个块只可以左右通过 | 表示这个块只可以上下通过 # 表示这个块不能通过 （从每个块只能走到其上下左右相邻的四个块）

输出

一个数，表示小明把所以可以通过的块都经过且只经过一次并回到原地的方案数。

样例

输入

Sample 1
2 2
..
..


Sample 2
Input:
4 4
....
..-.
....
....

输出

Output 1
1


Output 2
1

提示

数据范围: 0 < N, M < 13 不保证答案在long 范围之内

时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题