Paths in a Grid with Traps

Masha is navigating a grid from the top-left corner to the bottom-right corner. The grid has a dimension of ( n ) rows and ( m ) columns. However, some cells contain traps, and stepping onto a trap is not allowed. Masha can only move either down or right. Your task is to calculate the number of safe paths from the start to the finish while avoiding traps, modulo (10^9+7).

The recurrence for the dynamic programming solution is given by:
[ dp[i][j] = \begin{cases} 0, & \text{if cell } (i, j) \text{ has a trap},\ dp[i-1][j] + dp[i][j-1], & \text{otherwise} \end{cases} ]
with the starting condition (dp[0][0] = 1) if the starting cell is trap free.

inputFormat

The input is given via standard input (stdin). The first line contains two integers ( n ) and ( m ) (the number of rows and columns respectively). The second line contains an integer ( k ) representing the number of traps. Each of the following ( k ) lines contains two integers ( x ) and ( y ), representing the 1-indexed coordinates of a trap.

outputFormat

Output a single integer on standard output (stdout) — the number of possible safe paths from the top-left to the bottom-right corner modulo (10^9+7).## sample

3 3
1
2 2

2