3060. 上下左右promax

上下左右promax

没错又是这道题,但是与之前不同的是,他升级了!

有一个的迷宫,在迷宫中的每一个格子都为'R','D','B'三种类型之一,'R'表示处于当前的格子时只能往右边走'D'表示处于当前的格子时只能往下边走,而'B'表示向右向下均可以走。

我们认为两个移动序列是不同的,当且仅当移动序列的长度不同,或者在某一步中采取了不同的移动方式。

迷宫的起点依旧是左上角,终点是右下角,请求出有多少种行走路径。

输入

多组输入,每组第一行两个整数

接下输入的矩阵表示地图,矩阵中中仅包含大写字母'D','R','B'。

输出

输出一个整数,表示方案数对 取余之后的结果。

样例

输入#1

5 5
RBBBR
BBBBB
BBBDB
BDBBB
RBBBB

输出#1

25



难度等级: 0
总通过次数: 11
总提交次数: 51