F. 棋盘路径计数

题目描述

给一个 $H \times W$ 的图，可以向下、右、右下方移动任意长度（不经过 #）。其中 . 表示可以通过，# 表示不可以通过。求从 $(1,1)$ 到 $(H,W)$ 有多少种方案，总方案数要取模 $10^9+7$。

输入格式

第一行两个整数 $H\ W$ 接下来 $H$ 行，每行一个长度为 $W$ 的字符串 $S_{i1}\dots S_{iW}$，表示第 $i$ 行的网格

输出格式

输出方案数，对 $10^9+7$ 取模

样例

输入样例#1

3 3
...
.#.
...

输出样例#1

10

输入样例#2

4 4
...#
...
..#.
....

输出样例#2

84

输入样例#3

8 10
..........
..........
..........
..........
..........
..........
..........
..........

输出样例#3

13701937

数据范围与提示

• $2 \le H,W \le 2000$
• $S_{ij}$ 是 # 或 .
• $S_{11}$ 与 $S_{HW}$ 都是 .