题目描述

在 $n imes m$ 网格中，从左上角出发，每次只能向右或向下走一格。. 表示可通行，# 表示障碍。求到达右下角的路径数，答案对 $1000000007$ 取模。

输入格式

第一行两个整数 $n,m$，随后 $n$ 行网格。

输出格式

输出合法路径数对 $1000000007$ 取模的结果。

样例

3 4
....
.#..
....

4

数据规模与约定

$1\le n,m\le1000$；起点或终点可能是障碍。