该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

徐老师最近又开始玩他的机器人了，这天他决定让机器人去参加一下现在很热门的《寻路比赛》

一开始他以为这是一个高端人工智能竞赛，需要机器人通过周围的环境自主判断路线并进行移动

结果发现这个比赛相当简单！

主办方会给出一张地图铺在地上，地图大小为 $n * m$，每个格子中会画一个英文指示符：$U,D,L,R$ 和一个数字 $G_{i,j}$

其中英文指示符表示当机器人踏入这个格子时，下一步只能向指示符对应的方向移动，UDLR 分别对应了 上下左右，而 $G_{i,j}$ 则表示当机器人踏入这个格子时的得分

为了增加比赛难度，主办方还额外增加了两项规则：

1. 由于机器人是一个人型机器人，所以在移动时必须左右脚交替移动，并且每次移动只能踏出一步，而当左脚踏入某个格子时，会获得 $G_{i,j}$ 点得分，如果是右脚踏入某个格子，则会扣掉 $G_{i,j}$ 点得分
2. 当机器人踏入一个格子，并且计算该格子的得分后，这个格子的数字 $G_{i,j}$ 将会变化为 $-G_{i,j}$，即相反数

比如机器人现在左脚踏入了格子 $(3,4)$，这个格子上的指示符为 $U$，数字 $G_{3,4}=3$，那么会获得 $3$ 点得分，并且下一步机器人将以右脚踏入 $(2,4)$ 并扣掉 $G_{2,4}$ 点得分

现在主办方会指定起点 $(st_i,st_j)$，并且要求所有选手的机器人必须以左脚踏入这个起点开始移动

在移动过程中，当机器人移动到地图外时，这一轮比赛就会结束，并且获得当前的得分

当然，选手也可以在机器人移动中途随时结束，不再让机器人继续移动，也可以获得当前的得分

这个问题对徐老师来说可太简单了，其他选手考虑的是如何从起点出发获得最高分

而徐老师考虑的就多了，他决定计算出以任意格子作为起点时的最高得分！

现在徐老师请你也一起来挑战这个问题，和他的答案做个对照

输入格式

输入第一行包含两个整数 $n,m$ 表示地图大小

接下来 $n$ 行，每行包含一个长度为 $m$ 的字符串，分别表示这一行中每个格子上的指示符

接下来 $n$ 行，每行包含 $m$ 个整数，分别表示这一行中每个格子上的数字 $G_{i,j}$

输出格式

由于答案过多，所以请你按照以下方式输出答案 $ans$

设 cnt[i][j] 表示以 (i,j) 为起点时的最大得分
const long long MOD = 1e9 + 7;
long long ans = 0, base = 1;
for (int i = 1; i <= n; ++i) {
	for (int j = 1; j <= m; ++j){
	    ans = (ans + cnt[i][j] * base % MOD) % MOD;
	    base = base * 131 % MOD;
	}
}

数据范围

对于 $10\%$ 的数据满足： $1 \leq n \leq 10$

对于 $40\%$ 的数据满足： $1 \leq n \leq 100$

对于另外 $10\%$ 的数据满足 $1 \leq n \leq 1000$ 且指示符只有可能是 $D$ 或者 $R$

对于 $100\%$ 的数据满足： $1 \leq n \leq 1000, -10^9 \leq G_{i,j} \leq 10^9$

保证指示符只有可能是 UDLR 其中一个大写字母

样例输入1

3 3
DRD
RUD
DLD
1 2 3
4 5 6
7 8 -1

样例输出1

-697283612

样例解释1

每个点出发的最大得分别是

3 6 3
5 6 7
7 8 -1

样例输入2

3 3
RRR
RRD
ULL
1 2 3
4 5 6
7 8 9

样例输出2

583610153

样例解释2

每个点出发的最大得分分别是

2 2 3
5 8 6
11 8 9