Counting Paths in a Grid with Rocks

You are given an (N \times M) grid. Your task is to determine the number of distinct paths from the top-left cell (1,1) to the bottom-right cell (N,M) by moving only down or right. Some cells in the grid contain rocks (obstacles) and cannot be traversed. A valid path must avoid all cells that have rocks. If either the starting cell or the destination cell is blocked by a rock, the answer is 0.

For example, in a 3 by 3 grid without any rocks, there are 6 valid paths. However, adding obstacles may reduce this number. The answer is guaranteed to fit into a 64-bit integer.

inputFormat

The input is read from standard input (stdin) and follows the format below:

The first line contains three integers (N), (M), and (K) separated by spaces, representing the number of rows, the number of columns, and the number of rocks respectively.
Each of the following (K) lines contains two integers, representing the 1-indexed row and column coordinates of a rock.

outputFormat

Output a single integer to standard output (stdout): the number of distinct valid paths from the top-left corner to the bottom-right corner that avoid cells with rocks.## sample

3 3 0

6