题目描述

迷宫是一个$\red{n ×}$ $\red{m}$的网格，第$\red{i}$第$\red{j}$列的格子会包含一个方向指示$\red{d_{i,j}}$和一个权值$\red{v_{i,j}}$。 假设起点为格子$\red{(sx, sy)（}$即第$\red{sx}$行第$\red{sy}$列的格子），一开始牛妹左脚踏入格子 $\red{(sx, sy)，}$分数加上$\red{v_{sx,sy} ，}$然后该格子的权值变为它的相反数?$\red{v_{sx,sy}}$。 之后有两种选择:

$\red{(1)}$结束游戏，当前分数为最终分数。

$\red{(2)}$按照当前格子的方向指示走到下一个格子$\red{(x, y)}$。如果踏入当前格子的是左脚， 则右脚踏入$\red{(x, y)，}$并且分数减去 $\red{v_{x,y}}$；如果踏入当前格子的是右脚，则左脚踏入 $\red{(x, y)，}$分数加上 $\red{v_{x,y}}$。之后$\red{v_{x,y}}$变为它的相反数?$\red{v_{x,y}}$。然后继续做下一个选择。 注意，必须存在下一个格子才能选择$\red{(2)，}$否则只能选择$\red{(1)}$。具体的下一个格子的 定义如下：

格子的方向指示由 $\red{^v<>}$ 四个字符表示，假设当前格子为$\red{(i, j)，}$

如果$\red{d_{i,j}= }$'^'，则表示往上走，即下一个格子为$\red{(i - 1, j)}$；

如果$\red{d_{i,j}= }$'$\red{v}$'，则表示往下走，即下一个格子为 $\red{(i + 1, j)}$；

如果$\red{d_{i,j}= }$'$\red{<}$'，则表示往左走，即下一个格子为$\red{(i, j - 1)}$；

如果$\red{d_{i,j}= }$'$\red{>}$'，则表示往右走，即下一个格子为 $\red{(i, j + 1)}$；

如果格子$\red{(i, j)}$的下一个格子$\red{(x, y)}$不满足$\red{1 ≤}$ $\red{x ≤}$ $\red{n}$且$\red{1 ≤}$ $\red{y ≤}$ $\red{m，}$那么认为格子 $\red{(i, j)}$不存在下一个格子。

牛妹的初始分数为 $\red{0，}$她想知道，对于每个$\red{(i, j) (1 ≤}$ $\red{i ≤}$ $\red{n, 1 ≤}$ $\red{j ≤}$ $\red{m)}$作为起点， 她能得到的最高的最终分数是多少。由于她不想输出文件太大，假设答案为

$\red{(ans_{i,j})_{n×m}，}$你只需要输出

$\red{\sum_{i=1}^{n}{\sum_{j=1}^{m}{(ans_{i,j}+B)C^{(i-1)m+j-1}mod2^{64}}}}$

其中$\red{B = 10^{15}, C = 2 \times10^{15} + 21}$。

如果以$\red{(i, j)}$为起点，能得到比任意正整数大的最终分数，则令 $\red{ans_{i,j} = B}$。

输入格式

第一行，两个正整数$\red{n, m，}$以空格相隔。

接下来$\red{n}$行，第$\red{i }$行是字符串$\red{di，}$其第$\red{j}$个字符（从 $\red{1 }$开始）$\red{d_{i,j}}$表示第$\red{i}$行第$\red{j}$列格子 的方向指示。

接下来$\red{n}$行，第$\red{i}$行$\red{m}$个整数 $\red{v_{i,1}, v_{i,2}, . . . , v_{i,m} ，}$以空格相隔，$\red{v_{i,j}}$表示第$\red{i}$行第$\red{j}$列格子 的初始权值。

输出格式

输出一个整数，表示答案。

样例

输入样例

3 3
><>
>vv
^<<
1 2 3
4 5 6
7 8 9

输出样例

3946712175731523781

提示

样例 $\red{1 }$说明

对应的答案为

$\red{1 2 3}$

$\red{7 ~5 ~6}$

$\red{8 ~8~ 17}$

数据范围

对于 $\red{10\%}$数据，满足$\red{1 ≤}$ $\red{n, m ≤}$ $\red{10}$。

对于 $\red{40\%}$数据，满足$\red{1 ≤}$ $\red{n, m ≤}$ $\red{100}$。

对于 $\red{100\%}$数据，满足$\red{1 ≤}$ $\red{n, m ≤}$ $\red{1000}$。

$\red{d_{i,j}= }$^或 $\red{v }$或 $\red{< }$或 $\red{>, -1e9 ≤}$ $\red{v_{i,j} ≤}$ $\red{1e9, , ∀1 ≤}$ $\red{i ≤}$ $\red{n, 1 ≤}$ $\red{j ≤}$ $\red{m}$。

注意：由于答案可能较大，对于 $\red{C/C++}$语言，你可能需要使用 $\red{long long}$ 数据 类型进行计算。在输出答案时，可能不需要实际的取模，只需要使用 $\red{unsigned }$ $\red{long long}$`数据类型的自然溢出即可