{"raw_statement":[{"iden":"statement","content":"_Qwerty78_ is a well known programmer (He is a member of the ICPC WF winning team in 2015, a topcoder target and one of codeforces top 10). \n\nHe wants to go to Dreamoon's house to apologize to him, after he ruined his plans in winning a Div2 contest (He participated using the handle _\"sorry_Dreamoon\"_) so he came first and Dreamoon came second.\n\nTheir houses are presented on a grid of N rows and M columns. Qwerty78 house is at the cell (1, 1) and Dreamoon's house is at the cell (N, M).\n\nIf Qwerty78 is standing on a cell (r, c) he can go to the cell (r + 1, c) or to the cell (r, c + 1). Unfortunately Dreamoon expected Qwerty78 visit , so he put exactly 1 obstacle in this grid (neither in his house nor in Qwerty78's house) to challenge Qwerty78. Qwerty78 can't enter a cell which contains an obstacle.\n\nDreamoon sent Qwerty78 a message \"In how many ways can you reach my house?\". Your task is to help Qwerty78 and count the number of ways he can reach Dreamoon's house. Since the answer is too large , you are asked to calculate it modulo 109 + 7 .\n\nThe first line containts a single integer T , the number of testcases.\n\nThen T testcases are given as follows :\n\nThe first line of each testcase contains two space-separated N , M ( 2 ≤ N, M ≤ 105)\n\nThe second line of each testcase contains 2 space-separated integers OR, OC - the coordinates of the blocked cell (1 ≤ OR ≤ N) (1 ≤ OC ≤ M).\n\nOutput T lines , The answer for each testcase which is the number of ways Qwerty78 can reach Dreamoon's house modulo 109 + 7.\n\nSample testcase Explanation :\n\nThe grid has the following form:\n\n_Q*._\n\n_..D_\n\nOnly one valid path:\n\n_(1,1)_ to _(2,1)_ to _(2,2)_ to _(2,3)_.\n\n"},{"iden":"input","content":"The first line containts a single integer T , the number of testcases.Then T testcases are given as follows :The first line of each testcase contains two space-separated N , M ( 2 ≤ N, M ≤ 105)The second line of each testcase contains 2 space-separated integers OR, OC - the coordinates of the blocked cell (1 ≤ OR ≤ N) (1 ≤ OC ≤ M)."},{"iden":"output","content":"Output T lines , The answer for each testcase which is the number of ways Qwerty78 can reach Dreamoon's house modulo 109 + 7."},{"iden":"examples","content":"Input12 31 2Output1"},{"iden":"note","content":"Sample testcase Explanation :The grid has the following form:_Q*.__..D_Only one valid path:_(1,1)_ to _(2,1)_ to _(2,2)_ to _(2,3)_."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**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 grid dimensions, with $ 2 \\leq N, M \\leq 10^5 $.  \n- Let $ (r_b, c_b) \\in \\{1, \\dots, N\\} \\times \\{1, \\dots, M\\} $ be the coordinates of the single obstacle, with $ (r_b, c_b) \\neq (1,1) $ and $ (r_b, c_b) \\neq (N,M) $.  \n- Let $ P = \\{(i,j) \\mid 1 \\leq i \\leq N, 1 \\leq j \\leq M\\} $ be the set of grid cells.  \n- A valid path is a sequence of cells from $ (1,1) $ to $ (N,M) $, moving only right ($ (r,c) \\to (r,c+1) $) or down ($ (r,c) \\to (r+1,c) $), avoiding $ (r_b, c_b) $.\n\n**Constraints**  \n1. $ 1 \\leq T \\leq \\text{unknown (but bounded by input size)} $  \n2. $ 2 \\leq N, M \\leq 10^5 $  \n3. $ 1 \\leq r_b \\leq N $, $ 1 \\leq c_b \\leq M $, $ (r_b, c_b) \\notin \\{(1,1), (N,M)\\} $\n\n**Objective**  \nFor each test case, compute the number of valid paths from $ (1,1) $ to $ (N,M) $ avoiding $ (r_b, c_b) $, modulo $ 10^9 + 7 $:  \n$$\n\\text{Answer} = \\binom{N+M-2}{N-1} - \\left( \\binom{r_b + c_b - 2}{r_b - 1} \\cdot \\binom{N - r_b + M - c_b}{N - r_b} \\right) \\pmod{10^9 + 7}\n$$","simple_statement":"You are given a grid of size N×M. Start at (1,1), end at (N,M). You can only move right or down. One cell (OR, OC) is blocked (not start or end). Count the number of paths from start to end avoiding the blocked cell, modulo 10^9+7.","has_page_source":false}