Distinct Paths in a Grid with Obstacles

You are given a grid of m rows and n columns. Some cells in the grid are blocked, and you cannot pass through them. Your task is to compute the number of distinct paths from the top-left corner (cell (1,1)) to the bottom-right corner (cell (m,n)), moving only to the right or down.

If either the starting cell or the destination cell is blocked, the answer is 0.

Since the answer might be very large, output it modulo $$1000000007$$.

inputFormat

The first line of input contains an integer T representing the number of test cases. Each test case is described as follows:

• The first line contains three space-separated integers: m (number of rows), n (number of columns), and k (number of blocked cells).
• The next k lines each contain two space-separated integers denoting the 1-indexed row and column of a blocked cell.

outputFormat

For each test case, output a single line containing the number of distinct paths from the top-left to the bottom-right of the grid modulo $$1000000007$$.

## sample

5
3 3 1
2 2
4 5 4
1 2
2 1
3 3
4 2
2 2 1
1 2
2 2 2
1 2
2 1
2 2 0

2
0
1
0
2

</p>