题目描述

一个房间被划分为 $N\times M$ 个单位格子，每个格子要么为空，要么是墙。入口位于 $(0,0)$，出口位于 $(N-1,M-1)$。

从格子 $(i,j)$ 出发，只允许向下移动到 $(i+1,j)$，或向右移动到 $(i,j+1)$；不能越界，也不能进入墙格。因此，从入口到出口可能存在若干条合法路径，也可能一条都没有。

现在要把每个空格染成黑色或白色。要求：每一条从入口到出口的合法路径上，恰好包含一个黑色格子。

求满足条件的染色方案数，对 $1000000007$ 取模。

输入格式

第一行输入两个整数 $N,M$。

接下来 $N$ 行，每行一个长度为 $M$ 的字符串：

• # 表示墙；
• - 表示空格。

输出格式

输出合法染色方案数模 $1000000007$ 的结果。

数据范围

• $2\le N,M\le 30$；
• $(0,0)$ 和 $(N-1,M-1)$ 一定为空格。

样例

3 3
---
---
---

5