You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

一片农田中被划分成了 $N$ 行和 $M$ 列的网格，其中一些格子已经被毁坏，无法种植农作物。

现在，农夫希望在尚未毁坏的格子中选择一些格子来种植农作物，以满足以下条件：如果一个人从农田的左上角坐标 $(0,0)$ 的格子出发，只向下或向右移动，最终到达右下角坐标 $(N-1, M-1)$，途中只经过尚未毁坏的格子，那么无论怎么走必然恰好经过一颗农作物（起点和终点也算经过）。

请计算农夫有多少种不同的方式来种植农作物，以满足上述条件，方案数对 $10^9+7$ 取模。

两种方案不同当且仅当存在一个格子在其中一种方案里种了农作物而在另一种方案里没有种。

输入格式

输入文件名为 plant.in。

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

接下来 $N$ 行，每行一个长为 $M$ 的串，描述农田被毁坏的情况。如果其中第 $i$ 行第 $j$ 个字符是 - 则表示格子 $(i-1,j-1)$ 没有被毁坏；如果是 # 则表示格子 $(i-1,j-1)$ 被毁坏了。保证 $(0,0)$ 和 $(N-1,M-1)$ 没有被毁坏。

输出格式

输出文件名为 plant.out。

一行一个非负整数表示农夫有多少种不同的方式来种植农作物，以满足上述条件，对 $10^9+7$ 取模。

3 3
---
---
---

5

样例解释 1

农夫种植农作物的可能如下：

1. $\{(0,0)\}$；
2. $\{(0,1),(1,0)\}$；
3. $\{(0,2),(1,1),(2,0)\}$；
4. $\{(2,1),(1,2)\}$；
5. $\{(2,2)\}$；

3 3
--#
##-
---

64

样例解释 2

不存在 $(0,0)$ 到 $(N-1,M-1)$ 的路径，所以任何种植方案都满足条件。有 $6$ 个格子可以选择种或不种，所以答案是 $2^6=64$。

5 8
------##
-##--#--
---#----
-----##-
#-------

432

数据范围与提示

对于 $100$ 的数据，有以下限制：$1\le N,M\le 30$，并且保证 $(0,0)$ 和 $(N-1,M-1)$ 没有被毁坏。

• 对于前 $10\%$ 的数据，限制进一步放宽：$1\le N,M\le 4$；
• 对于接下来的 $40\%$ 的数据，没有被毁坏的格子，且 $(N,M)$ 的取值有多种情况，包括 $(5,5)$、$(5,15)$、$(5,30)$、$(10,10)$、$(15,15)$、$(20,20)$、$(25,25)$、$(30,30)$，每种情况各占总数据的 $5\%$。