题目描述
给你一个 n 行 m 列的二维迷宫,一开始你在迷宫的左上角的格子 1,1 处(我们用位置 (x.y) 来表示第 x 行第 y 列),你要走到右下角的格子 (n,m) 处,行走的方向是有规定的:每一步你只能往右移动一格,或者往下移动一格,并且不能移动出迷宫的边界;迷宫中 . 为可走的格子,* 为滑滑梯,可以直接滑到当前方向的下一个 .,但是不能滑出边界(即如果没有下一个 .,就不能向这个方向滑滑梯,简称碰都不能碰的滑梯)
请问在这种限制下,你有多少种不同的移动方案。
说明:只要从起点到终点的移动路线不同,那么我们就说它们是不同的移动方案。
比如:假设n=2,m=3 ,并且迷宫形状如样例 1 一样的时候,从左上角 (1,1) 移动到右下角 (2,3) 共有 2 种移动方案(1,1)->(1.3)->(2,3) , (1,1)->(2,1)->(2,3);
输入格式
从文件 maze.in 中读入数据。
输入一行包含两个正数n,m ,以空格分隔
接下来 n 行每行包含一个长度为 m 的字符串,用于描述这个二维迷宫。数据保证 (1,1) 一定是 .
输出格式
输出到文件 maze.out 中。
输出包含一个整数,表示从 (1.1) 走到 (n.m) 的方案数模 10^9 + 7
样例1输入
2 3
..
..
样例1输出
2