#2406. 推箱子

推箱子

【题目描述】

在一个 n × m 的棋盘上有若干个箱子,其中 (1, 1) 一定是空地。你将从 (1, 1) 出发,每次 你可以选择向右移动一个或者向下移动一格,最终到达 (n, m).

由于箱子的存在,你的前进路上会多出许多限制,为了清除障碍,当你向下移动或向右移 动时,如果你即将移动到的位置有箱子,你可以把箱子向你移动的方向推开,由于你的力气非 常的大,你可以同时推动在同一直线上的任意多个箱子。由于某些原因,你不能将箱子退出棋 盘,也就是说,如果你的移动会造成箱子被推出棋盘,那么你不能进行这个移动。

你需要求出从 (1, 1) 到 (n, m) 有多少种不同的可行的路径,由于答案可能很大,你只需要 输出答案对109+710^9 + 7 取模的结果

【输入格式】

第一行两个整数 n, m 接下来 n 行,

每行一个长度为 m 的字符串,表示这个棋盘上每个位置上有没有箱子,其 中字符. 表示这个位置是空地,字符 R 表示这个位置上有箱子。

【输出格式】

一行一个整数,表示答案。

【输入样例 1】

1 1
.

【输出样例 1】

1

【输入样例 2】

2 3 
...
..R

【输出样例 2】

0

###【数据范围与提示】

对于 20%20\% 的数据,保证 n,m8n, m ≤ 8

对于另外 10%10\% 的数据,棋盘上没有箱子

对于另 20%20\% 的数据,棋盘上至多有一个箱子

对于另 30%30\% 的数据,n,m300n, m ≤ 300

对于 100%100\% 的数据,保证 1n,m20001 ≤ n, m ≤ 2000