F. Count Ways
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

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.

Input

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 (xi, yi), denoting the blocked cell’s coordinates.

Output

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

Constraints

  • 1 ≤ T ≤ 10
  • 1 ≤ N, M ≤ 105
  • 0 ≤ K ≤ 103
  • 1 ≤ xi ≤ N
  • 1 ≤ yi ≤ M
Examples
Input
2
3 2 0
2 3 1
1 2
Output
3
1
Note

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).