Unique Paths Avoiding Blocked Zones

You are given a grid with dimensions \( (N+1) \times (M+1) \) where the top-left cell is \( (0,0) \) and the bottom-right cell is \( (N,M) \). You need to compute the number of unique paths from the start to the destination. You can only move right or down at each step.

Some cells are under construction (blocked) and cannot be traversed. If either the starting cell \( (0,0) \) or the ending cell \( (N,M) \) is blocked, the answer is 0. Otherwise, use dynamic programming with the recurrence

\( dp[i][j] = dp[i-1][j] + dp[i][j-1] \)

when \( (i,j) \) is not blocked, while making sure that blocked cells contribute 0 to the path count.

inputFormat

The input is read from standard input (stdin) and has the following format:

1. The first line contains three integers: \( N \), \( M \) and \( K \), where \( N \) and \( M \) specify the destination cell \( (N, M) \) and \( K \) is the number of blocked cells.
2. The next \( K \) lines each contain two space-separated integers \( x \) and \( y \) representing the coordinates of a blocked cell.

If \( K = 0 \), there are no blocked cells and no additional lines will follow.

outputFormat

Output a single integer indicating the number of unique paths from \( (0, 0) \) to \( (N,M) \) avoiding the blocked cells. The output should be printed to standard output (stdout).

3 3 2
1 2
2 1

2