問題文
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