Distinct Shortest Paths in a Blocked Grid

You are given a grid of size \(n \times m\) representing a city with \(n\) vertical streets and \(m\) horizontal avenues. You start at the top-left cell \((1,1)\) and want to reach the bottom-right cell \((n,m)\) by only moving right or down. Some cells (blocks) in the grid are blocked and cannot be stepped on.

Your task is to compute the number of distinct shortest paths from \((1,1)\) to \((n,m)\) that avoid these blocked cells. A shortest path is defined as a path that moves only right or down and has exactly \((n-1)+(m-1)\) moves.

The formula for the number of moves is:

[ \text{Total Moves} = n + m - 2 ]

Note that if the starting cell or the destination cell is blocked, the answer is \(0\).

inputFormat

The input is given from stdin and has the following format:

n m k
r1 c1
 r2 c2
 ...
 rk ck

On the first line, three integers \(n\), \(m\), and \(k\) are provided, where \(n\) and \(m\) represent the grid dimensions, and \(k\) denotes the number of blocked cells. Each of the following \(k\) lines contains two integers \(r\) and \(c\) representing the row and column of a blocked cell. If \(k = 0\), then no further input lines follow.

outputFormat

Output a single integer to stdout: the number of distinct shortest paths from \((1,1)\) to \((n,m)\) that do not pass through any blocked cell.

## sample

3 3 1
2 2

2