问题 E: 网格路径数
内存限制：1024 MB
时间限制：2.000 S
评测方式：文本比较
命题人：
提交：14
解决：4
题目描述
有一个$H$行$W$列的网格S，$S_{i,j}$为'#'表示此网格是一堵墙不能通行，为'.'则可以通行。你初始站在$(1,1)$处，在不碰到墙的前提下，每次可以向右走任意格，或向下走任意格，或沿对角线走任意格。请问有多少种方案到$(H,W)$?
对于任意两个方案，如果存在第$i$次移动使它的位置不同，视为不同方案。
答案对$(10^9+7)$取模。
对于任意两个方案，如果存在第$i$次移动使它的位置不同，视为不同方案。
答案对$(10^9+7)$取模。
输入
$H$ $W$
$S_{1,1}$ . . . $S_{1,W}$
.
.
.
$S_{H,1}$ . . . $S_{H,W}$
$2<=H,W<=2000$
$(1,1)$和 $(H,W)$一定不是墙
$S_{1,1}$ . . . $S_{1,W}$
.
.
.
$S_{H,1}$ . . . $S_{H,W}$
$2<=H,W<=2000$
$(1,1)$和 $(H,W)$一定不是墙
输出
输出取模后的方案数
样例输入 复制
3 3
...
.#.
...
样例输出 复制
10