#dph. [dp_h]Grid 1

[dp_h]Grid 1

题目描述

有一个由 HH 行和 WW 列组成的网格。用 (i,j)(i, j) 表示从上往下第 ii 行、从左往右第 jj 列的方格。

对于每个 iijj (1iH1 \leq i \leq H, 1jW1 \leq j \leq W),方格 (i,j)(i, j) 用字符 ai,ja_{i, j} 描述。如果 ai,ja_{i, j}.,方格 (i,j)(i, j) 为空方格;如果 ai,ja_{i, j}#,方格 (i,j)(i, j) 是墙方格。保证方格 (1,1)(1, 1)(H,W)(H, W) 是空方格。

Taro 从方格 (1,1)(1, 1) 出发,通过重复向右或向下移动到相邻的空方格,最终到达 (H,W)(H, W)

找出 Taro 从方格 (1,1)(1, 1)(H,W)(H, W) 的路径数。由于答案可能非常大,要将计数结果对 109+710^9 + 7 取模。

约束条件

  • HHWW 是整数。
  • 2H,W10002 \leq H, W \leq 1000
  • ai,ja_{i, j}.#
  • 方格 (1,1)(1, 1)(H,W)(H, W) 是空方格。

输入

输入将从标准输入读取,并具有以下格式:

HH WW a1,1a1,Wa_{1, 1}\ldots a_{1, W} \ldots aH,1aH,Wa_{H, 1}\ldots a_{H, W}

输出

打印 Taro 从方格 (1,1)(1, 1)(H,W)(H, W) 的路径数,对 109+710^9 + 7 取模。


示例输入1

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

示例输出1

3

共有三条路径:


示例输入2

5 2
..
#.
..
.#
..

示例输出2

0

可能没有路径。


示例输入3

5 5
..#..
.....
#...#
.....
..#..

示例输出3

24

示例输入4

20 20
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................

示例输出4

345263555

请务必对计数结果取模 109+710^9 + 7