Robot Paths Avoiding Dangerous Cells

In this problem, you are given an n x m grid and a set of dangerous cells that the robot must avoid. The robot starts at the top-left cell (0,0) and needs to reach the bottom-right cell (n-1, m-1) by moving only to the right or down. You need to find the number of distinct paths available such that the robot never steps on a dangerous cell. The result is to be computed modulo $10^9+7$.

The recurrence relation behind the solution is given by:

$$dp[i][j] = \begin{cases} 0, & \text{if } (i,j) \text{ is dangerous;} \\ (dp[i-1][j] + dp[i][j-1]) \bmod (10^9+7), & \text{otherwise.} \end{cases} $$

Note that if the starting cell (0,0) is marked as dangerous, then the answer is 0. Similarly, if the destination (n-1,m-1) is dangerous, no valid path exists.

This is a classic dynamic programming problem on a grid with constraints, and careful handling of boundaries is required.

inputFormat

The input is read from standard input (stdin). The first line contains three integers n, m, and k, where n and m denote the number of rows and columns respectively, and k represents the number of dangerous cells. The following k lines each contain two integers r and c, indicating that the cell (r, c) is dangerous. It is guaranteed that 0 ≤ r < n and 0 ≤ c < m.

outputFormat

Output one integer on a single line: the number of distinct paths from (0, 0) to (n-1, m-1) avoiding dangerous cells, computed modulo $10^9+7$.## sample

3 3 1
1 1

2

</p>