Unique Safe Paths in a Grid

You are given a grid of size \( m \times n \) and a list of mines (obstacles) located at specific cells. Your task is to compute the number of unique safe paths from the top-left corner \((0,0)\) to the bottom-right corner \((m-1,n-1)\), moving only right or down, while avoiding any cell containing a mine.

Important conditions:

• If the starting cell or the destination cell contains a mine, then the answer is \(0\).
• The coordinates of the mines are given using 0-indexing.

The path count should be computed using dynamic programming. Formally, if \(dp[i][j]\) denotes the number of ways to reach cell \((i,j)\), then for a safe cell \((i,j)\) (i.e. not mined), the recurrence is given by:

[ dp[i][j] = \begin{cases} 1, & \text{if } i = 0 \text{ and } j = 0, \ dp[i-1][j] + dp[i][j-1], & \text{otherwise}, \end{cases} ]

provided that the adjacent cells are safe. Otherwise, if the cell is mined, \(dp[i][j]=0\).

inputFormat

The input is read from stdin and consists of:

1. The first line contains two integers \(m\) and \(n\) representing the number of rows and columns of the grid.
2. The second line contains an integer \(k\) representing the number of mines.
3. The next \(k\) lines each contain two integers, representing the 0-indexed row and column positions of a mine.

outputFormat

Output a single integer to stdout — the number of unique safe paths from the top-left corner to the bottom-right corner of the grid.

## sample

5 5
0

70

</p>