题目描述

给定 $n\times m$ 个网格的状态，每个网格的状态以一个字符表示

• * 表示这个单元格不需要铺砖，也不能铺砖
• . 表示这个单元格需要铺砖，也必须铺砖

只有一种形状为 $1\times 2$ 的长方形砖块，数量无限多，请问有多少种不同的铺砖方案将所有需要铺砖的单元格铺满，由于答案可能很大，输出方案数模 $1,000,000,007$ 的余数。

输入格式

• 第一行：两个整数 $n$ 与 $m$
• 第二行到第 $n+1$ 行：每行 $m$ 个字符表示每个单元格的类型，保证只有 . 与 *

输出格式

• 单个整数：表示方案数模 $1,000,000,007$ 的余数

3 3
...
.*.
...

2

2 4
....
....

5

数据范围

• $30\%$ 的数据 $1\leq n, m\leq 6$
• $60\%$ 的数据 $1\leq n, m\leq 12$
• $100\%$ 的数据 $1\leq n, m\leq 18$