给出一个 $n \times m$ 大小的网格状棋盘，其中 $1 \le n \le 2$。棋盘上的某些格子是被阻挡的，其余格子是空闲的。你可以在两个相邻且均为空闲的格子上放置一个骨牌（大小为 $1 \times 2$ 或 $2 \times 1$ 的矩形）。一旦你在棋盘上放置了一个骨牌，它所占用的两个格子就会变成被阻挡状态。如果在一个给定的棋盘上放置了某个骨牌集合中的所有骨牌后，无法再在棋盘上放置任何更多的骨牌，则称该骨牌集合对该棋盘是好的。
给定一个棋盘，问存在多少个不同的好的骨牌集合？结果对 $10^9 + 7$ 取模。如果两个骨牌中有一个占用了另一个没有占用的格子，则认为这两个骨牌是不同的。如果一个骨牌集合中包含另一个集合中不存在的骨牌，反之亦然，则认为这两个骨牌集合是不同的。
输入格式
第一行包含两个整数 $n$ 和 $m$（$1 \le n \le 2$，$1 \le m \le 10^5$）。
接下来的 $n$ 行，每行包含 $m$ 个字符，每个字符为 . 或 #。
第 $i$ 行的第 $j$ 个字符如果为 .，表示格子 $(i, j)$ 是空闲的；如果为 #，表示格子 $(i, j)$ 是被阻挡的。
输出格式
输出一个整数，表示好的骨牌集合的数量对 $10^9 + 7$ 取模后的结果。
数据范围
- $1 \le n \le 2$
- $1 \le m \le 10^5$
子任务
| 子任务 | 分值 | 限制条件 |
|---|---|---|
| 1 | 6 | $m \le 2$ |
| 2 | 14 | $n = 1$ |
| 3 | 12 | $m \le 7$ |
| 4 | 8 | $3 \mid m$，对于 $j = 3k$（$k$ 的范围为 $1$ 到 $\frac{m}{3}$），格子 $(1, j - 2)$、$(1, j - 1)$ 和 $(2, j - 2)$ 是空闲的，所有其他格子都被阻挡 |
| 5 | 12 | 所有格子均为空闲 |
| 6 | 18 | $m \le 10^3$ |
| 7 | 30 | 无附加限制 |
样例
输入格式 1
2 2 .. ..
输出格式 1
2
输入格式 2
2 3 ##. #.#
输出格式 2
1
输入格式 3
1 8 ....#...
输出格式 3
4
说明
- 在第一个样例中，有两个可能的好的集合：一个包含两个垂直骨牌，另一个包含两个水平骨牌。
- 在第二个样例中，唯一好的集合是空集。