Unique Paths in Grid with Restricted Cells

You are given an ( m \times n ) grid where a robot starts at the top-left cell (cell ((1,1))) and must reach the bottom-right cell (cell ((m,n))) by moving only right or down. Some cells are restricted and cannot be stepped on. You are also provided with an integer ( k ) and a list of ( k ) restricted cells (given as 1-indexed coordinates). Calculate the number of unique paths from the start to the destination while avoiding restricted cells. The answer should be given modulo ( 10^9+7 ).

inputFormat

The input is read from stdin. The first line contains two integers ( m ) and ( n ) representing the number of rows and columns, respectively. The second line contains an integer ( k ), the number of restricted cells. This is followed by ( k ) lines, each containing two integers ( r ) and ( c ) which represent the 1-indexed row and column of a restricted cell.

outputFormat

Output a single integer to stdout representing the number of unique paths from the top-left to the bottom-right cell modulo ( 10^9+7 ).## sample

3 3
1
2 2

2