問題文

H * W のマス目があり、それぞれのマスには整数が書かれています。 i 行 j 列に書かれている数は a_{ij} です。

あなたはこのグリッドの中の好きなマスから好きなだけ動きます(最初のマスから動かなくてもかまいません)。 今いるマスの上下左右に隣接しているマスのうち、今いるマスより大きな整数が書かれたマスに移動することができます。

ありうる移動経路の個数を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