Taco Path Counting Problem

You are given a grid with M rows and N columns. You start at the top‐left cell, which is denoted by (1,1), and want to reach the bottom‐right cell (M,N). You are only allowed to move either right or down.

Some cells in the grid are blocked and cannot be traversed. If the starting cell (1,1) or the destination cell (M,N) is blocked, then there are 0 valid paths.

Your task is to count the number of different paths from the start to the destination modulo \(10^9+7\).

The blocked cells are given as a set of coordinates. Each test case begins with two integers, M and N, followed by an integer K which denotes the number of blocked cells. Then follow K lines, each containing two integers representing the row and column of a blocked cell.

inputFormat

The input is read from standard input (stdin) and has the following format:

T
M N
K
x1 y1
x2 y2
... (K lines)
... (repeat the above for T test cases)

Here, T is the number of test cases. For each test case, the first line contains two integers M and N, the dimensions of the grid. The next line contains an integer K, the number of blocked cells, followed by K lines each having two integers which denote the coordinates of a blocked cell. The coordinates are 1-indexed.

outputFormat

For each test case, output a single integer on a new line indicating the number of valid paths from (1,1) to (M,N) modulo \(10^9+7\), read from standard output (stdout).

## sample

2
3 3
1
2 2
3 3
2
1 2
2 1

2
0

</p>