Question
Unique Forest Paths
You are given an m × n integer matrix representing a forest area.
A traveler starts at the top-left corner (0, 0) of the forest and wants to reach the bottom-right corner (m−1, n−1).
The traveler can move only down or right at any moment.
-
A 1 represents a tree (an obstacle that cannot be crossed).
-
A 0 represents an open path.
Your task is to determine the number of unique routes the traveler can take to reach the destination without passing through any trees.
Since the answer can be very large, print it modulo 10⁹ + 7.
Input
The first line contains two space-separated integers m and n — representing the number of rows and columns of the grid.
The next m lines each contain n space-separated integers (either 0 or 1), representing the grid.
Note :
Since the answer may be very large, print it modulo 1e9 + 7.
The next m lines each contain n space-separated integers (either 0 or 1), representing the grid.
Note :
Since the answer may be very large, print it modulo 1e9 + 7.
Output
Print the number of ways to reach the bottom-right corner of the grid starting from the top-left corner taking modulo 1e9 + 7.
Example
Input:
3 3
0 0 0
0 1 0
0 0 0
Output:
2
Explanation:
There is one obstacle in the middle of the 3x3 grid above.
There are two ways to reach the bottom-right corner:
1. Right -> Right -> Down -> Down
2. Down -> Down -> Right -> Right
3 3
0 0 0
0 1 0
0 0 0
Output:
2
Explanation:
There is one obstacle in the middle of the 3x3 grid above.
There are two ways to reach the bottom-right corner:
1. Right -> Right -> Down -> Down
2. Down -> Down -> Right -> Right