{"problem":{"name":"F. Count Ways","description":{"content":"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","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10058F"},"statements":[{"statement_type":"Markdown","content":"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).\n\nBut K cells are blocked in the matrix(you can’t visit a blocked cell). You are given coordinates of all these cells.\n\nYou have to count number of ways to reach cell (N, M) if you begin at cell (1, 1).\n\nTwo ways are same if and only if path taken is exactly same in both ways.\n\nFirst 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.\n\nFor each test case print the required answer modulo 109 + 7 in one line.\n\n*Constraints* \n\nExample test case 1:\n\nNo cell is blocked. 3 distinct paths are: \n\nExample test case 2: Only one valid path: \n\n## Input\n\nFirst 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.\n\n## Output\n\nFor 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 \n\n[samples]\n\n## Note\n\nExample 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).","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ T \\in \\mathbb{Z} $ be the number of test cases.  \nFor each test case:  \n- Let $ N, M \\in \\mathbb{Z}^+ $ denote the dimensions of the grid, with cells indexed from $ (1,1) $ to $ (N,M) $.  \n- Let $ K \\in \\mathbb{Z}_{\\geq 0} $ denote the number of blocked cells.  \n- Let $ B = \\{ (x_i, y_i) \\mid i \\in \\{1, \\dots, K\\} \\} \\subseteq \\{1, \\dots, N\\} \\times \\{1, \\dots, M\\} $ be the set of blocked cells.  \n\n**Constraints**  \n1. $ 1 \\leq T \\leq \\text{unspecified} $  \n2. $ 1 \\leq N, M \\leq \\text{unspecified} $  \n3. $ 0 \\leq K \\leq N \\cdot M $  \n4. All blocked cells $ (x_i, y_i) $ satisfy $ 1 \\leq x_i \\leq N $, $ 1 \\leq y_i \\leq M $, and are distinct.  \n5. Start cell $ (1,1) $ and end cell $ (N,M) $ are not blocked.  \n\n**Objective**  \nCompute the number of paths from $ (1,1) $ to $ (N,M) $, moving only right or down, avoiding all blocked cells in $ B $, modulo $ 10^9 + 7 $.  \n\nLet $ P(i,j) $ denote the number of valid paths from $ (1,1) $ to $ (i,j) $.  \nThen:  \n$$\nP(i,j) =\n\\begin{cases}\n0 & \\text{if } (i,j) \\in B \\\\\n1 & \\text{if } (i,j) = (1,1) \\\\\nP(i-1,j) + P(i,j-1) & \\text{otherwise (for } i \\geq 1, j \\geq 1 \\text{)}\n\\end{cases}\n$$  \nwith $ P(i,j) = 0 $ if $ i < 1 $ or $ j < 1 $.  \n\nOutput $ P(N,M) \\mod (10^9 + 7) $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10058F","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}