Harddp
Grid Paths with Obstacles
Time limit 2 s · Memory 64 MBAcceptance: —Solved by: 0
Statement
The first line contains n and m. Each of the next n lines contains m numbers: 0 is a free cell, 1 is an obstacle. Print the number of paths from the top-left cell to the bottom-right cell moving only right or down and never entering an obstacle, modulo 10^9 + 7. If the start or the end cell is blocked, the answer is 0.
Examples
Example 1
Input
3 3 0 0 0 0 1 0 0 0 0
Output
2
Example 2
Input
1 1 0
Output
1
Constraints
- 1 ≤ n, m ≤ 300