How many paths? P84609


Statement
 

pdf   zip

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
    Salvador Roura
    Language
    English
    Translator
    Salvador Roura
    Original language
    Catalan
    Other languages
    Catalan
    Official solutions
    C++
    User solutions
    C++