Problem Description

There is a grid of $ H * W $ cells, each containing an integer. The number written in the cell at the $ i $-th row and $ j $-th column is $ a_{ij} $.

You can start from any cell in this grid and move as many times as you like (you may choose not to move from the starting cell). You can move to a cell that is adjacent to the current cell (up, down, left, or right) if the integer in that cell is greater than the integer in the current cell.

Find the number of possible paths, modulo $ 10^9+7 $.

Input Format

The input is given from the standard input in the following format:

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

Output Format

Output the number of paths modulo $ 10^9+7 $.

Sample Input and Output

Sample Input #1

2 3
1 4 5
2 4 9

Sample Output #1

18

Sample Input #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

Sample Output #2

170

Notes/Hints

Constraints

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

Sample Explanation 1

For example, there are paths starting from the cell at the 1st row and 2nd column, moving right and then down, or starting from the cell at the 1st row and 1st column, moving down. There are a total of 18 paths.

见题面 Input 部分

见题面 Output 部分