疯狂的水管工 Mirko 被雇佣去建设城市中两个位置之间的供水网络。城市地图可以用一个 $R \times S$ 的网格来表示。某些格子不适合放置水管。Mirko 需要连接的两个位置分别位于网格左上角格子的正上方，以及右下角格子的正下方。

每个适合放置水管的格子，Mirko 既可以将其留空，也可以在其中放置以下 6 种水管之一：

求有多少种放置水管的方法，使得能够用一条连续的水管连接这两个位置（水不能溢出）。所有放置的水管都必须被使用。

输出方案数模 10007 的余数。

输入格式

输入的第一行包含两个整数 $R$ 和 $S$（$2 \le R, S \le 10$），分别表示城市网格的行数 and 列数。

接下来的 $R$ 行，每行包含恰好 $S$ 个字符：如果该格子适合放置水管，则为 .；如果不适合，则为 #。

输出格式

输出唯一的一行，包含所需的方案数模 10007 的余数。

样例

输入格式 1

2 3
...
.#.

输出格式 1

1

输入格式 2

3 3
...
...
...

输出格式 2

12

说明

第一个样例说明：这是唯一可能的解决方案：