Ural 1519 Formula 1

尽管 Vologda 没能取得举办 20** 年冬季奥运会的资格，但众所周知，这座城市将举办一场一级方程式赛事。为了这样一件大事，除了旅馆、饭店和国际机场之外，还要新修一条赛道，一切都为了即将涌入这座城市的一级方程式车迷。

但是当所有旅馆和一半的饭店建好之后，人们发现，未来赛道的场地上住着许多地鼠，它们都住在自己的洞里。由于我们非常爱护动物，环保人士绝不会允许把赛道修在这些洞上面。于是市长现在正愁坐在办公室里，看着标满了地鼠洞的赛道地图。

Vologda 的赛道设计得相当简单：它是一个 $N\times M$ 个格子大小的矩形，每一个非障碍格子中都要恰好修建一段赛道。每一段赛道都必须与矩形的某条边平行，因此赛道上只会出现直角弯。

用形式化的语言描述：给定一个 $n\times m$ 的棋盘，其中有些格子存在障碍（地鼠洞），求经过所有非障碍格子恰好一次的哈密顿回路的个数。

输入格式

第一行包含两个整数 $N$ 和 $M$ 。

接下来 $N$ 行，每行包含 $M$ 个字符，表示矩形中对应的格子。字符 .（句点）表示这个格子中要修建一段赛道，字符 *（星号）表示这个格子里有一个地鼠洞。

输出所求的方案数。保证答案不超过 $2^{63}-1$ 。

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

本题为 Ural 1519 试题「Formula 1」，题面与测试数据整理自 BZOJ 1814。

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