题目描述

有一座 $n\times m$ 的矩形城市，每个格点位置都有一栋房屋。给定一个由 . 和 # 组成的网格：. 表示房屋开放，# 表示房屋上锁。

约翰需要进行一次巡游，并满足：

• 每栋开放房屋恰好访问一次；
• 不能访问上锁房屋；
• 每一步只能移动到上下左右相邻的房屋；
• 第一栋访问的房屋必须位于城市边界；
• 最后一栋访问的房屋也必须位于城市边界。

两条巡游方案只要访问房屋的顺序不同，就视为不同方案。因此同一条无向路径的两个相反方向通常是两种不同方案。

求访问全部开放房屋的合法巡游方案数。保证答案可以用有符号 64 位整数表示。

输入格式

第一行一个整数 $n$，表示行数。

接下来 $n$ 行，每行一个由 . 和 # 组成的字符串。所有字符串长度相同，其长度即为 $m$。

输出格式

输出一个整数，表示合法巡游方案数。

数据范围

• $1\le n,m\le100$；
• $1\le nm\le100$；
• 至少存在一个 .。

样例 1

3
....
.##.
....

20

样例 2

3
....
.###
....

2