C++程序题：迷宫路径

给定 n×m 个方格构成的图，每个格子都有一种地形：

有一些格子是墙，以符号 X 表示，墙不可通行。

有一些格子是空地，以符号 . 表示，空地可以通行。

请统计从左上角的方格出发，有多少种不同的路线可以以最短距离走到右下角。在行走过程中，不能进入地形为墙的方格，保证起点与终点方格地形不是墙。且行走时，只能移动到水平或垂直方向相邻的方格。

由于方案数可能很大，输出模 1,000,000,007 的余数。

输入格式

第一行：单个整数 n 与 m

第二行到第 n+1 行：第 i+1 行每行有 m 个整数表示第 i 行的地形

输出格式

单个整数：表示路线方案模 1,000,000,007 的余数。

输入样例

3 3
...
.X.
...

输出样例

说明提示

30% 的数据，1 ≤ n, m ≤ 4

60% 的数据，1 ≤ n, m ≤ 10

100% 的数据，1 ≤ n, m ≤ 1000

限制

时间限制：1000ms，内存限制：500MiB