该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

量子芯片的完美布局 (Perfect Layout of a Quantum Chip)

背景故事

22 世纪，人类在量子计算领域取得了划时代的突破。全球最顶尖的量子科技公司 奇点矩阵（Singularity Matrix） 正在研发一款革命性的量子处理器。它的核心由一块 N × M 的矩形光子晶格构成。

在这片晶格中，有些位置是稳定的光子源，有些是深邃的光子阱，而绝大部分单元格都是等待填充的空间。设计师需要在这些源与阱之间铺设光波导，让量子态能够在芯片上稳定传输。

然而，首席架构师面临的难题是前所未有的：

• 每一对指定的端点（源或阱）必须用一条独立的光波导精确连接；
• 光波导之间不能交叉、不能合并、不能重叠；
• 更苛刻的是，为了最大化芯片的量子干涉效率，所有非障碍单元格必须被某条光波导覆盖，不能留下任何"闲置空间"。

这意味着整个晶格需要被完全填充成一个由不相交路径组成的完美网络。可能的设计数目浩如烟海，而工程团队没有精力一一验证。于是，他们将问题交给你——一名算法专家。你的任务是计算：一共有多少种合法的"完美布局"。

问题描述

你得到一个 $N \times M$ 的网格，其中：

• . 表示 空单元格，可以铺设光波导；
• # 表示 障碍物，禁止铺设；
• * 表示 端点，它是光波导的起点或终点。

需要用一系列路径将所有端点配对，且满足以下条件：

1. 端点配对：每个端点必须且只能作为一条路径的起点或终点，所有端点必须成对出现。

2. 路径规则：路径由一系列上下左右相邻的单元格组成，单元格必须是空格或端点。

3. 完全覆盖：所有空单元格必须被某条路径覆盖。

4. 路径独立：任意两条路径不能交叉，也不能共享同一个单元格。

5. 禁止闭环：不允许出现不含端点的闭合回路；每个连通分量恰好有两个端点。

最终，你需要输出满足条件的完美布局方案数。由于答案可能非常大，请对 $1,000,000,007$ 取模。

输入格式

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

接下来 $N$ 行，每行一个长度为 $M$ 的字符串，表示网格布局。

输出格式

输出一个整数，表示方案总数，对 $1,000,000,007$ 取模。

样例

样例输入 #1

2 2
*.
.*

样例输出 #1

0

样例解释 #1

这是一个 2×2 的网格，有 2 个端点和 2 个空单元格。不能存在闭环

*-.
| |
.-*

样例输入 #2

3 3
*.*
...
*.*

样例输出 #2

0

样例解释 #2

有4个端点，奇偶性矛盾。同色端点之间的简单路径包含奇数个格子。要用两条不相交路径把所有 9 个格子都覆盖，则两条路径的格子数之和应为 9（奇数），但两条“奇数长度”的路径之和必为偶数，矛盾。

样例输入 #3

2 3
*.*
*.*

样例输出 #2

3

样例解释 #23

左右两条横线：(0,0)-(0,1)-(0,2) 与 (1,0)-(1,1)-(1,2)； 左列竖线配右侧折线：(0,0)-(1,0) 与 (0,2)-(0,1)-(1,1)-(1,2)； 左侧折线配右列竖线：(0,0)-(0,1)-(1,1)-(1,0) 与 (0,2)-(1,2)。

数据范围

• $1 \leq N, M \leq 10$
• 端点数量为偶数，且 $0 \leq$ 端点数量 $\leq 10$
• 保证所有空单元格和端点构成连通区域