You are given a grid of size N \times M. Each cell (i, j) (where 0 \le i < N and 0 \le j < M) contains a positive integer A_{i,j}. This integer represents the exact distance a grasshopper must jump if it is currently at that cell.
From cell
(i, j), the grasshopper can make a single jump to one of the following two locations:
Cell (i + A_{i,j}, j), provided that i + A_{i,j} < N.
Cell (i, j + A_{i,j}), provided that j + A_{i,j} < M.
The grasshopper starts at the top-left cell (0, 0). Your task is to find the total number of distinct paths the grasshopper can take to reach the bottom-right cell (N-1, M-1). Because the number of paths can be very large, output the answer modulo 10^9 + 7.
Input
The first line contains two integers N and M (1 \le N, M \le 500), representing the number of rows and columns in the grid.
Each of the following N lines contains M space-separated integers A_{i,j} (1 \le A_{i,j} \le 10^6), representing the required jump distance from cell (i, j).
Output
Print a single integer: the number of distinct paths from (0, 0) to (N-1, M-1) modulo 10^9 + 7.
Examples
| standard input | standard output |
|---|
| 3 3
1 1 1
1 1 1
1 1 1
| 6
|
| 4 4
2 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
| 8
|