Grid Paths with Enemies

You are given an N x M grid. You must calculate the number of ways to move from the top-left corner to the bottom-right corner by only moving right or down. However, some cells are occupied by enemies and cannot be passed through.

The enemies are given as a list of coordinates in the format (row, column), and the grid cells are 1-indexed. If the starting cell or ending cell is occupied by an enemy, the answer is 0.

The answer should be computed modulo \(10^9+7\).

Input Format: The first line contains three integers \(N, M, K\) where \(N\) is the number of rows, \(M\) is the number of columns, and \(K\) is the number of enemy cells. Then K lines follow, each containing two integers representing the enemy's row and column.

Output Format: Output a single integer representing the number of ways to reach the bottom-right corner modulo \(10^9+7\).

inputFormat

The input is given via stdin in the following format:

N M K
r1 c1
r2 c2
... (K lines total, each representing an enemy cell's row and column)

If K = 0, then no enemy coordinates are provided.

outputFormat

Output a single integer via stdout, which is the number of ways to reach the bottom-right corner from the top-left corner modulo \(10^9+7\).

## sample

3 3 0

6