Question
Count Safe Paths in Grid
You are given a grid of size KaTeX can only parse string typed expression consisting of integers. Your task is to count the number of paths from the top-left cell KaTeX can only parse string typed expression to the bottom-right cell KaTeX can only parse string typed expression such that you never step on a negative cell. You can only move either right or down at any step. Since the number of paths can be large, print the answer modulo KaTeX can only parse string typed expression.
Input
The first line contains two integers KaTeX can only parse string typed expression and KaTeX can only parse string typed expression — the number of rows and columns in the grid.
The next KaTeX can only parse string typed expression lines each contain KaTeX can only parse string typed expression integers representing the grid — KaTeX can only parse string typed expression.
The next KaTeX can only parse string typed expression lines each contain KaTeX can only parse string typed expression integers representing the grid — KaTeX can only parse string typed expression.
Output
Print a single integer — the number of valid paths from KaTeX can only parse string typed expression to KaTeX can only parse string typed expression such that all visited cells are non-negative, modulo KaTeX can only parse string typed expression.
Example
Input
3 3
1 2 3
4 -1 6
7 8 9
Output
2
Explanation
The valid paths are:
(0,0) → (0,1) → (0,2) → (1,2) → (2,2)
(0,0) → (1,0) → (2, 0) → (2,1) → (2,2)
All cells on both of these paths are non-negative, so the answer is 2.
Input
3 3
1 4 3
4 -1 -1
-1 8 9
Output
0
Explanation
There are no valid paths from (0, 0) to (2, 2).
3 3
1 2 3
4 -1 6
7 8 9
Output
2
Explanation
The valid paths are:
(0,0) → (0,1) → (0,2) → (1,2) → (2,2)
(0,0) → (1,0) → (2, 0) → (2,1) → (2,2)
All cells on both of these paths are non-negative, so the answer is 2.
Input
3 3
1 4 3
4 -1 -1
-1 8 9
Output
0
Explanation
There are no valid paths from (0, 0) to (2, 2).