問題概要

n×m のグリッドからなる迷路を考えます。各セル (i, j) には方向指示 d_i,j と重み v_i,j が設定されています。プレイヤーは初期位置 (sx, sy) から左足で踏み込み、その時点で v_sx,sy を加算し、セルの重みを -v_sx,sy に反転させます。

その後、各ステップで以下の選択肢があります：

1. ゲームを終了し、現在のスコアを最終スコアとする
2. 現在のセルの方向指示に従って次のセル (x, y) に移動する

選択肢2を選んだ場合：

• 現在のセルに左足で踏み入れていた場合：右足で (x, y) に踏み込み、スコアから v_x,y を減算
• 現在のセルに右足で踏み入れていた場合：左足で (x, y) に踏み込み、スコアに v_x,y を加算
• 移動後、v_x,y を -v_x,y に反転させる

方向指示のルール：

• '^'：上方向へ移動 (i-1, j)
• 'v'：下方向へ移動 (i+1, j)
• '<'：左方向へ移動 (i, j-1)
• '>'：右方向へ移動 (i, j+1)

次のセルがグリッド範囲外の場合は選択肢2を選べません。

全てのセル (i, j) を起点とした場合の最大最終スコア ans_i,j を求め、以下の式で与えられるハッシュ値を出力してください：

Σ_i=1ⁿ Σ_j=1^m (ans_i,j + B) × C^(i-1)m+j-1 (mod 2⁶⁴)

ただし、B = 10¹⁵、C = 2×10¹⁵ + 21 です。

もし (i, j) を起点として無限に大きなスコアを得られる場合、ans_i,j = B とします。

入力形式

最初の行：2つの正整数 n, m（スペース区切り）

続く n 行：各行が文字列 d_i（方向指示）

続く n 行：各行が m 個の整数 v_i,1, v_i,2, ..., v_i,m（スペース区切り）

出力形式

1つの整数（ハッシュ値）を出力

サンプル入力

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

サンプル出力

3946712175731523781

サンプル説明

各セルを起点とした場合の最大スコア行列：

1 2 3
7 5 6
8 8 17

制約

• 10% のデータ：1 ≤ n, m ≤ 10
• 40% のデータ：1 ≤ n, m ≤ 100
• 100% のデータ：1 ≤ n, m ≤ 1000
• d_i,j ∈ {'^', 'v', '<', '>'}
• -10⁹ ≤ v_i,j ≤ 10⁹

注意：C/C++ を使用する場合、unsigned long long 型の自然なオーバーフローを利用して mod 2⁶⁴ を実現できます。