Count Paths

All submissions for this problem are available.
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 (x_{i}, y_{i}), denoting the blocked cell’s coordinates.
Output
For each test case print the required answer modulo 10^{9}+7 in one line.
Constraints
 1 ≤ T ≤ 10
 1 ≤ N, M ≤ 10^{5}
 0 ≤ K ≤ 10^{3}
 1 ≤ x_{i} ≤ N
 1 ≤ y_{i} ≤ M
Example
Input: 2 3 2 0 2 3 1 1 2 Output: 3 1
Explanation
Example test case 1.
No cell is blocked.
3 distinct paths are:
(1,1) > (1,2) > (2,2) > (3,2).
(1,1) > (2,1) > (2,2) > (3,2).
(1,1) > (2,1) > (3,1) > (3,2).
Example test case 2.
Only one valid path (1,1) > (2,1) > (2,2) > (2,3).
Author:  tanmaysahay94 
Tags  tanmaysahay94 
Date Added:  2022015 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, JAVA 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions