← 返回题目列表

AtCoder · abc037_d

D. 路线

中文机器翻译题面 查看原题

問題文

H * W 个方格,每个方格上都写着一个整数。 i 行 j 列中写入的数字是 a_{ij} 。

您可以从该网格中的任何方格移动任意距离(不必从第一个方格移动)。 您可以移动到与您当前所在方格的顶部、底部、左侧和右侧相邻的方格中,整数大于您当前所在方格的方格。

可能的移动路线数量为 除以10^9+7求余数。


制約

  • 1 \leq H, W \leq 1,000
  • 1 \leq a_{ij} \leq 10^9

入力

输入是按以下格式从标准输入给出的。

H W
a_{11} .. a_{1W}
:
a_{H1} .. a_{HW}

出力

移动路线数 打印除以10^9+7后的余数。


入力例 1

2 3
1 4 5
2 4 9

出力例 1

18

例如,1 行 2 从列开始向右下移动的路线, 1 行 1 有些路线从一列开始并向下移动。

总而言之 有 18 种路线。


入力例 2

6 6
1 3 4 6 7 5
1 2 4 8 8 7
2 7 9 2 7 2
9 4 2 7 6 5
2 8 4 6 7 6
3 7 9 1 2 7

出力例 2

170