{"raw_statement":[{"iden":"statement","content":"Two lovely snakes Kiki and Susu like to play in a rectangular field divided into equal-sized squares. For us, it doesn't 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 5 × 5, Kiki's length is 3 and Susu's length is also 3): \n\nYour program will be tested on one or more test cases. The first line of the input contains T (1  ≤  T  ≤  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  ≤  n,m  ≤  100000) and (2  ≤  k,s  ≤  min(n,m)).\n\nFor 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.\n\n"},{"iden":"input","content":"Your program will be tested on one or more test cases. The first line of the input contains T (1  ≤  T  ≤  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  ≤  n,m  ≤  100000) and (2  ≤  k,s  ≤  min(n,m))."},{"iden":"output","content":"For 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."},{"iden":"examples","content":"Input42 2 2 23 3 3 32 3 2 24 4 3 2OutputCase 1: 16Case 2: 48Case 3: 88Case 4: 1056"}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n, m \\in \\mathbb{Z}^+ $ denote the height and width of the rectangular grid.  \nLet $ k, s \\in \\mathbb{Z}^+ $ denote the lengths of Kiki and Susu, respectively.  \nEach snake occupies a contiguous sequence of $ k $ (resp. $ s $) unit squares in a single row (horizontal) or column (vertical).  \n\n**Constraints**  \n1. $ 1 \\leq T \\leq 1000 $  \n2. For each test case:  \n   - $ 2 \\leq n, m \\leq 100000 $  \n   - $ 2 \\leq k, s \\leq \\min(n, m) $  \n3. Snakes must be entirely within the grid.  \n4. Snakes must not overlap (no shared square).  \n\n**Objective**  \nCompute the number of valid starting configurations $(C_1, C_2)$, where:  \n- $ C_1 $ is a placement of Kiki (length $ k $) either horizontally or vertically.  \n- $ C_2 $ is a placement of Susu (length $ s $) either horizontally or vertically.  \n- $ C_1 \\cap C_2 = \\emptyset $.  \n\nLet:  \n- $ H_k = (n)(m - k + 1) $: number of horizontal placements of Kiki.  \n- $ V_k = (m)(n - k + 1) $: number of vertical placements of Kiki.  \n- $ H_s = (n)(m - s + 1) $: number of horizontal placements of Susu.  \n- $ V_s = (m)(n - s + 1) $: number of vertical placements of Susu.  \n\nTotal configurations without overlap constraint:  \n$$\nT_{\\text{total}} = (H_k + V_k)(H_s + V_s)\n$$\n\nSubtract overlapping configurations:  \nLet $ O $ be the number of pairs $(C_1, C_2)$ where the snakes overlap.  \n\nOverlap occurs only if:  \n- One is horizontal and the other vertical, and their rectangles intersect.  \n\nFor Kiki horizontal and Susu vertical:  \n- Kiki occupies row $ i $, columns $ j $ to $ j+k-1 $.  \n- Susu occupies column $ j' $, rows $ i' $ to $ i'+s-1 $.  \n- They overlap iff $ i \\in [i', i'+s-1] $ and $ j' \\in [j, j+k-1] $.  \n\nNumber of such overlapping pairs:  \n$$\nO_{\\text{hv}} = \\sum_{i=1}^n \\sum_{j=1}^{m-k+1} \\sum_{i'=1}^{n-s+1} \\sum_{j'=1}^{m-s+1} \\mathbf{1}_{i \\in [i', i'+s-1] \\land j' \\in [j, j+k-1]}\n$$\n\nThis simplifies to:  \n$$\nO_{\\text{hv}} = (n - s + 1)(m - k + 1)(s)(k)\n$$\n\nSimilarly, for Kiki vertical and Susu horizontal:  \n$$\nO_{\\text{vh}} = (n - k + 1)(m - s + 1)(k)(s)\n$$\n\nTotal overlapping pairs:  \n$$\nO = O_{\\text{hv}} + O_{\\text{vh}} = ks \\left[ (n - s + 1)(m - k + 1) + (n - k + 1)(m - s + 1) \\right]\n$$\n\nThus, the number of valid configurations is:  \n$$\n\\boxed{\n\\left[ (n(m - k + 1) + m(n - k + 1)) \\cdot (n(m - s + 1) + m(n - s + 1)) - ks \\left( (n - s + 1)(m - k + 1) + (n - k + 1)(m - s + 1) \\right) \\right] \\mod 1000000007\n}\n$$","simple_statement":"Given a grid of size n × m, place two snakes of lengths k and s such that:\n\n- Each snake is placed in a straight line (horizontal or vertical).\n- Both snakes are completely inside the grid.\n- The snakes do not overlap (no shared squares).\n\nCount the number of ways to place both snakes, modulo 1000000007.","has_page_source":false}