AT_abc037_d [ABC037D] 経路

[problemUrl]: https://atcoder.jp/contests/abc037/tasks/abc037_d $ H\ *\ W $ のマス目があり、それぞれのマスには整数が書かれています。 $ i $ 行 $ j $ 列に書かれている数は $ a_{ij} $ です。 あなたはこのグリッドの中の好きなマスから好きなだけ動きます(最初のマスから動かなくてもかまいません)。 今いるマスの上下左右に隣接しているマスのうち、今いるマスより大きな整数が書かれたマスに移動することができます。 ありうる移動経路の個数を$ 10^9+7 $で割った余りを求めてください。

入力は以下の形式で標準入力から与えられる。 > $ H $ $ W $ $ a_{11} $ .. $ a_{1W} $ : $ a_{H1} $ .. $ a_{HW} $

移動経路の個数を$ 10^9+7 $で割った余りを出力せよ。

### 制約 - $ 1\ \leq\ H,\ W\ \leq\ 1,000 $ - $ 1\ \leq\ a_{ij}\ \leq\ 10^9 $ ### Sample Explanation 1 例えば、$ 1 $ 行 $ 2 $ 列から出発し、右、下と移動する経路や、 $ 1 $ 行 $ 1 $ 列から出発し、下に移動する経路などがあります。 全部で $ 18 $ 種類の経路があります。