Consider an *n* × *m* matrix
where each cell (*i*, *j*) has a number *x*_{ij}
to indicate that you can jump down to a distance
(measured as number of cells) between 1 and *x*_{ij},
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 *x*_{ij} 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 10^{9} + 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
- Salvador Roura
- Language
- English
- Translator
- Salvador Roura
- Original language
- Catalan
- Other languages
- Catalan
- Official solutions
- C++
- User solutions
- C++