Unique Paths with Obstacles

You are given a grid with m rows and n columns. The top-left cell is the starting point and the bottom-right cell is the destination. You can only move to the right or down at each step. However, some cells are marked as obstacles and cannot be traversed.

Formally, define \(dp[i][j]\) as the number of ways to reach cell \((i, j)\) from the starting cell \((0,0)\). The recurrence relation is given by:

\[ dp[i][j] = \begin{cases} dp[i-1][j] + dp[i][j-1] & \text{if } (i,j) \text{ is not an obstacle} \\ 0 & \text{if } (i,j) \text{ is an obstacle} \end{cases} \]

If the starting or ending cell is an obstacle, the answer is 0. Your task is to compute the number of unique paths from the top-left cell to the bottom-right cell, avoiding any obstacles.

inputFormat

The input is given from standard input as follows:

• The first line contains three integers: m, n, and k, representing the number of rows, the number of columns, and the number of obstacles respectively.
• The next k lines each contain two integers, representing the row and column indices of an obstacle cell (0-indexed).

outputFormat

Output a single integer to standard output: the number of unique paths from the top-left to the bottom-right cell, avoiding obstacles.

## sample

3 3 0

6