{"trustable":true,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027$$$$$$\u0027, right: \u0027$$$$$$\u0027, display: true},\n {left: \u0027$$$\u0027, right: \u0027$$$\u0027, display: false},\n {left: \u0027$$\u0027, right: \u0027$$\u0027, display: true},\n {left: \u0027$\u0027, right: \u0027$\u0027, display: false}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eTwo lovely snakes Kiki and Susu like to play in a rectangular field divided into equal-sized squares. For us, it doesn\u0027t matter what the rules of the game play are, but we are interested in the rules of the starting. These rules are: 1- Each snake must lie in either a vertical or a horizontal line. 2- Both snakes must be inside the garden (their whole bodies are inside). 3- No snake can share a square in the field with the other snake. The following figure shows some valid and invalid cases of starting (in case of a field of size \u003cspan class\u003d\"tex-span\"\u003e5 × 5\u003c/span\u003e, Kiki\u0027s length is 3 and Susu\u0027s length is also 3): \u003c/p\u003e\u003ccenter\u003e \u003cimg class\u003d\"tex-graphics\" src\u003d\"CDN_BASE_URL/d3c028849c07e059be3e061e461cad74?v\u003d1726221094\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\" width\u003d\"567px\"\u003e \u003c/center\u003e Kiki and Susu are very confused and they don\u0027t know how to start the game, so they are asking you for help. Kiki and Susu will tell you what is the size of the grid and what are the lengths of them themselves, and you have to tell them in how many ways they can start the game. Note: the case in which a snake\u0027s head is at \u003cspan class\u003d\"tex-span\"\u003e(\u003ci\u003ex\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e1\u003c/sub\u003e, \u003ci\u003ey\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e1\u003c/sub\u003e)\u003c/span\u003e and its tail is at \u003cspan class\u003d\"tex-span\"\u003e(\u003ci\u003ex\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e2\u003c/sub\u003e, \u003ci\u003ey\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e2\u003c/sub\u003e)\u003c/span\u003e is considered different from the case in which the snake\u0027s head is at \u003cspan class\u003d\"tex-span\"\u003e(\u003ci\u003ex\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e2\u003c/sub\u003e, \u003ci\u003ey\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e2\u003c/sub\u003e)\u003c/span\u003e and its tail is at \u003cspan class\u003d\"tex-span\"\u003e(\u003ci\u003ex\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e1\u003c/sub\u003e, \u003ci\u003ey\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e1\u003c/sub\u003e)\u003c/span\u003e. "}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eYour program will be tested on one or more test cases. The first line of the input contains T (1 \u003cspan class\u003d\"tex-span\"\u003e ≤ \u003c/span\u003e T \u003cspan class\u003d\"tex-span\"\u003e ≤ \u003c/span\u003e 1000) the number of test cases following. Each test case consists of a single line containing 4 space separated integers n,m,k,s representing the length of the field, the width of the field, the length of Kiki and the length of Susu respectively. For each test case, these constraints hold: (2 \u003cspan class\u003d\"tex-span\"\u003e ≤ \u003c/span\u003e n,m \u003cspan class\u003d\"tex-span\"\u003e ≤ \u003c/span\u003e 100000) and (2 \u003cspan class\u003d\"tex-span\"\u003e ≤ \u003c/span\u003e k,s \u003cspan class\u003d\"tex-span\"\u003e ≤ \u003c/span\u003e min(n,m)).\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eFor each test case print a single line containing \"Case c: \" without quotes where c is the number of the test case, and then the number of ways in which the two snakes can start their game modulo 1000000007.\u003c/p\u003e"}},{"title":"Examples","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\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\u003e4\n2 2 2 2\n3 3 3 3\n2 3 2 2\n4 4 3 2\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eCase 1: 16\nCase 2: 48\nCase 3: 88\nCase 4: 1056\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}