{"trustable":true,"prependHtml":"\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027\\\\(\u0027, right: \u0027\\\\)\u0027, display: false},\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eChiaki has an \u003cvar\u003en\u003c/var\u003e × \u003cvar\u003em\u003c/var\u003e matrix \u003cvar\u003eA\u003c/var\u003e. Rows are numbered from 1 to \u003cvar\u003en\u003c/var\u003e from top to bottom and columns are numbered from 1 to \u003cvar\u003em\u003c/var\u003e from left to right. The element in the \u003cvar\u003ei\u003c/var\u003e-th row and the \u003cvar\u003ej\u003c/var\u003e-th column is \u003cvar\u003eA\u003c/var\u003e\u003csub class\u003d\"lower-index\"\u003e\u003cvar\u003ei\u003c/var\u003e, \u003cvar\u003ej\u003c/var\u003e\u003c/sub\u003e.\u003c/p\u003e\u003cp\u003eLet \u003cvar\u003eM\u003c/var\u003e({\u003cvar\u003ei\u003c/var\u003e\u003csub class\u003d\"lower-index\"\u003e1\u003c/sub\u003e, \u003cvar\u003ei\u003c/var\u003e\u003csub class\u003d\"lower-index\"\u003e2\u003c/sub\u003e, ..., \u003cvar\u003ei\u003c/var\u003e\u003csub class\u003d\"lower-index\"\u003e\u003cvar\u003es\u003c/var\u003e\u003c/sub\u003e}, {\u003cvar\u003ej\u003c/var\u003e\u003csub class\u003d\"lower-index\"\u003e1\u003c/sub\u003e, \u003cvar\u003ej\u003c/var\u003e\u003csub class\u003d\"lower-index\"\u003e2\u003c/sub\u003e, ..., \u003cvar\u003ej\u003c/var\u003e\u003csub class\u003d\"lower-index\"\u003e\u003cvar\u003et\u003c/var\u003e\u003c/sub\u003e}) be the matrix that results from deleting row \u003cvar\u003ei\u003c/var\u003e\u003csub class\u003d\"lower-index\"\u003e1\u003c/sub\u003e, \u003cvar\u003ei\u003c/var\u003e\u003csub class\u003d\"lower-index\"\u003e2\u003c/sub\u003e, ..., \u003cvar\u003ei\u003c/var\u003e\u003csub class\u003d\"lower-index\"\u003e\u003cvar\u003es\u003c/var\u003e\u003c/sub\u003e and column \u003cvar\u003ej\u003c/var\u003e\u003csub class\u003d\"lower-index\"\u003e1\u003c/sub\u003e, \u003cvar\u003ej\u003c/var\u003e\u003csub class\u003d\"lower-index\"\u003e2\u003c/sub\u003e, ..., \u003cvar\u003ej\u003c/var\u003e\u003csub class\u003d\"lower-index\"\u003e\u003cvar\u003et\u003c/var\u003e\u003c/sub\u003e of \u003cvar\u003eA\u003c/var\u003e and \u003cvar\u003ef\u003c/var\u003e({\u003cvar\u003ei\u003c/var\u003e\u003csub class\u003d\"lower-index\"\u003e1\u003c/sub\u003e, \u003cvar\u003ei\u003c/var\u003e\u003csub class\u003d\"lower-index\"\u003e2\u003c/sub\u003e, ..., \u003cvar\u003ei\u003c/var\u003e\u003csub class\u003d\"lower-index\"\u003e\u003cvar\u003es\u003c/var\u003e\u003c/sub\u003e}, {\u003cvar\u003ej\u003c/var\u003e\u003csub class\u003d\"lower-index\"\u003e1\u003c/sub\u003e, \u003cvar\u003ej\u003c/var\u003e\u003csub class\u003d\"lower-index\"\u003e2\u003c/sub\u003e, ..., \u003cvar\u003ej\u003c/var\u003e\u003csub class\u003d\"lower-index\"\u003e\u003cvar\u003et\u003c/var\u003e\u003c/sub\u003e}) be the number of saddle points in matrix \u003cvar\u003eM\u003c/var\u003e({\u003cvar\u003ei\u003c/var\u003e\u003csub class\u003d\"lower-index\"\u003e1\u003c/sub\u003e, \u003cvar\u003ei\u003c/var\u003e\u003csub class\u003d\"lower-index\"\u003e2\u003c/sub\u003e, ..., \u003cvar\u003ei\u003c/var\u003e\u003csub class\u003d\"lower-index\"\u003e\u003cvar\u003es\u003c/var\u003e\u003c/sub\u003e}, {\u003cvar\u003ej\u003c/var\u003e\u003csub class\u003d\"lower-index\"\u003e1\u003c/sub\u003e, \u003cvar\u003ej\u003c/var\u003e\u003csub class\u003d\"lower-index\"\u003e2\u003c/sub\u003e, ..., \u003cvar\u003ej\u003c/var\u003e\u003csub class\u003d\"lower-index\"\u003e\u003cvar\u003et\u003c/var\u003e\u003c/sub\u003e}).\u003c/p\u003e\u003cp\u003eChiaki would like to find all the value of \u003cvar\u003ef\u003c/var\u003e({\u003cvar\u003ei\u003c/var\u003e\u003csub class\u003d\"lower-index\"\u003e1\u003c/sub\u003e, \u003cvar\u003ei\u003c/var\u003e\u003csub class\u003d\"lower-index\"\u003e2\u003c/sub\u003e, ..., \u003cvar\u003ei\u003c/var\u003e\u003csub class\u003d\"lower-index\"\u003e\u003cvar\u003es\u003c/var\u003e\u003c/sub\u003e}, {\u003cvar\u003ej\u003c/var\u003e\u003csub class\u003d\"lower-index\"\u003e1\u003c/sub\u003e, \u003cvar\u003ej\u003c/var\u003e\u003csub class\u003d\"lower-index\"\u003e2\u003c/sub\u003e, ..., \u003cvar\u003ej\u003c/var\u003e\u003csub class\u003d\"lower-index\"\u003e\u003cvar\u003et\u003c/var\u003e\u003c/sub\u003e}). As the output may be very large ((2\u003csup class\u003d\"upper-index\"\u003e\u003cvar\u003en\u003c/var\u003e\u003c/sup\u003e - 1)(2\u003csup class\u003d\"upper-index\"\u003e\u003cvar\u003em\u003c/var\u003e\u003c/sup\u003e - 1) matrix in total), she is only interested in the value \u003c/p\u003e\u003ccenter class\u003d\"tex-equation\"\u003e\u003cimg align\u003d\"middle\" class\u003d\"tex-formula\" src\u003d\"CDN_BASE_URL/5e8bff8e8510d774f6baf2ed4622edae?v\u003d1726224125\" alt\u003d\"$\\left(\\sum_{\\begin{array}{r} 1 \\le i_1 \u003c \\dots \u003c i_s \\le n \\\\ 1 \\le j_1 \u003c \\dots \u003c j_t \\le m \\\\ 0 \\le s \u003c n \\\\ 0 \\le t \u003c m\\end{array}} f(\\{i_1,i_2,\\dots,i_s\\},\\{j_1,j_2,\\dots,j_t\\})\\right) \\bmod (10^9+7).$\"\u003e\u003c/center\u003e\u003cp\u003e\u003c/p\u003e\u003cp\u003eNote that a saddle point of a matrix is an element which is both the only largest element in its column and the only smallest element in its row.\u003c/p\u003e\n\n\u003ch4\u003eInput\u003c/h4\u003e\n\n\u003cp\u003eThere are multiple test cases. The first line of input contains an integer \u003cvar\u003eT\u003c/var\u003e, indicating the number of test cases. For each test case:\u003c/p\u003e\n\n\u003cp\u003eThe first line contains four integers \u003cvar\u003en\u003c/var\u003e and \u003cvar\u003em\u003c/var\u003e (1 ≤ \u003cvar\u003en\u003c/var\u003e, \u003cvar\u003em\u003c/var\u003e ≤ 1000) -- the number of rows and the number of columns.\u003c/p\u003e\n\n\u003cp\u003eEach of the next \u003cvar\u003en\u003c/var\u003e lines contains \u003cvar\u003em\u003c/var\u003e integer \u003cvar\u003eA\u003c/var\u003e\u003csub class\u003d\"lower-index\"\u003e\u003cvar\u003ei\u003c/var\u003e, 1\u003c/sub\u003e, \u003cvar\u003eA\u003c/var\u003e\u003csub class\u003d\"lower-index\"\u003e\u003cvar\u003ei\u003c/var\u003e, 2\u003c/sub\u003e, ..., \u003cvar\u003eA\u003c/var\u003e\u003csub class\u003d\"lower-index\"\u003e\u003cvar\u003ei\u003c/var\u003e, \u003cvar\u003em\u003c/var\u003e\u003c/sub\u003e (1 ≤ \u003cvar\u003eA\u003c/var\u003e\u003csub class\u003d\"lower-index\"\u003e\u003cvar\u003ei\u003c/var\u003e, \u003cvar\u003ej\u003c/var\u003e\u003c/sub\u003e ≤ 10\u003csup class\u003d\"upper-index\"\u003e6\u003c/sup\u003e), where \u003cvar\u003eA\u003c/var\u003e\u003csub class\u003d\"lower-index\"\u003e\u003cvar\u003ei\u003c/var\u003e, \u003cvar\u003ej\u003c/var\u003e\u003c/sub\u003e is the integer in the \u003cvar\u003ei\u003c/var\u003e-th row and the \u003cvar\u003ej\u003c/var\u003e-th column.\u003c/p\u003e\n\n\u003cp\u003eIt is guaranteed that neither the sum of all \u003cvar\u003en\u003c/var\u003e nor the sum of all \u003cvar\u003em\u003c/var\u003e exceeds 5000.\u003c/p\u003e\n\n\u003ch4\u003eOutput\u003c/h4\u003e\n\n\u003cp\u003eFor each test case, output an integer denoting the answer.\u003c/p\u003e\n\n\u003ch4\u003eSample\u003c/h4\u003e\n\u003ctable class\u003d\"vjudge_sample\"\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e2\n2 2\n1 1\n1 1\n4 5\n1 2 3 4 5\n6 7 8 9 10\n11 12 13 14 15\n16 17 18 19 20\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e4\n465\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\n"}}]}