401938: GYM100589 F Count Ways

You have a N x M matrix of cells. The cell (i,  j) represents the cell at row i and column j. You can go from one cell (i,  j) only down or right, that is to cells (i  +  1,  j) or (i,  j  +  1).

But K cells are blocked in the matrix(you can’t visit a blocked cell). You are given coordinates of all these cells.

You have to count number of ways to reach cell (N, M) if you begin at cell (1, 1).

Two ways are same if and only if path taken is exactly same in both ways.

First line consists of T, denoting the number of test cases. Each test case consists of N, M and K in single line. Each of the next K lines contains two space separated integers (x_i, y_i), denoting the blocked cell’s coordinates.

For each test case print the required answer modulo 10⁹ + 7 in one line.

Constraints

• 1 ≤ T ≤ 10
• 1 ≤ N, M ≤ 10⁵
• 0 ≤ K ≤ 10³
• 1 ≤ x_i ≤ N
• 1 ≤ y_i ≤ M

2
3 2 0
2 3 1
1 2

3
1

Example test case 1:

No cell is blocked. 3 distinct paths are:

• (1, 1) to (1, 2) to (2, 2) to (3, 2).
• (1, 1) to (2, 1) to (2, 2) to (3, 2).
• (1, 1) to (2, 1) to (3, 1) to (3, 2).

Example test case 2: Only one valid path:

• (1, 1) to (2, 1) to (2, 2) to (2, 3).