Paths Around the Walls

Difficulty: 1500 2000 ms 128 MB

dp

Count the right/down paths from the top-left to the bottom-right of a grid, avoiding wall cells (#), modulo 10⁹+7.

Input: the first line has N and M; the next N lines each have M characters (. free, # wall).

Output: the number of paths mod 10⁹+7.

Constraints:

• 1 ≤ N, M ≤ 1000

Sample Tests

3 3
...
.#.
...

2

1 1
.

1

Read the Editorial