# How many paths? P84609

Statement html

Consider an n × m matrix where each cell (i, j) has a number xij to indicate that you can jump down to a distance (measured as number of cells) between 1 and xij, either vertically, diagonally to the left, or diagonally to the right. If we call (0, 0) the upper left position, all the visited cells must have coordinates between 0 and n for the rows (this includes a row below the last one), and between 0 and m − 1 for the columns. The goal is to start at row 0, and get exactly to row n. How many paths exist?

Input

Input consists of several cases, each with n, m, and n rows with m natural numbers. Suppose that n, m and the xij are between 1 and 100.

Output

For every case, print the number of paths that begin at any cell in the top row and end in any cell just below the bottom row, modulo 109 + 7.

Public test cases
• Input

```1 1
1

1 3
1 1 1

2 3
1 1 1
1 1 1

5 1
99
99
99
99
99

3 4
3 7 6 3
1 2 4 2
5 1 2 9
```

Output

```1
7
17
16
110
```
• Information
Author