题目描述

一个 $n \times m$ 的棋盘,有些的格子存在障碍,求经过所有非障碍格子的哈密顿回路个数。

输入格式

The first line contains the integer numbers N and M (2 ≤ N, M ≤ 12). Each of the next N lines contains M characters, which are the corresponding cells of the rectangle. Character "." (full stop) means a cell, where a segment of the race circuit should be built, and character "*" (asterisk) - a cell, where a gopher hole is located.

输出格式

You should output the desired number of ways. It is guaranteed, that it does not exceed 2^63-1.

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

2

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

6