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++