障碍路径计数

普及⏱ 1000ms💾 256MB#P5040

题目描述

$n \times m$ 网格,部分格子是障碍(#)。从左上角走到右下角,每步只能向右或向下,不能经过障碍。求路径条数对 $10^9+7$ 取模的结果。保证起点与终点不是障碍。

输入格式

第一行两个整数 $n$$m$;接下来 $n$ 行每行 $m$ 个字符(.#)。

输出格式

一行一个整数,即模 $10^9+7$ 后的路径数。

数据范围

$$1 \le n,m \le 200$$

样例输入 #1
1 1
.
样例输出 #1
1
样例输入 #2
1 5
..#..
样例输出 #2
0