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):
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)).
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.
## Input
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)).
## Output
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.
[samples]
**Definitions**
Let $ n, m \in \mathbb{Z}^+ $ denote the height and width of the rectangular grid.
Let $ k, s \in \mathbb{Z}^+ $ denote the lengths of Kiki and Susu, respectively.
Each snake occupies a contiguous sequence of $ k $ (resp. $ s $) unit squares in a single row (horizontal) or column (vertical).
**Constraints**
1. $ 1 \leq T \leq 1000 $
2. For each test case:
- $ 2 \leq n, m \leq 100000 $
- $ 2 \leq k, s \leq \min(n, m) $
3. Snakes must be entirely within the grid.
4. Snakes must not overlap (no shared square).
**Objective**
Compute the number of valid starting configurations $(C_1, C_2)$, where:
- $ C_1 $ is a placement of Kiki (length $ k $) either horizontally or vertically.
- $ C_2 $ is a placement of Susu (length $ s $) either horizontally or vertically.
- $ C_1 \cap C_2 = \emptyset $.
Let:
- $ H_k = (n)(m - k + 1) $: number of horizontal placements of Kiki.
- $ V_k = (m)(n - k + 1) $: number of vertical placements of Kiki.
- $ H_s = (n)(m - s + 1) $: number of horizontal placements of Susu.
- $ V_s = (m)(n - s + 1) $: number of vertical placements of Susu.
Total configurations without overlap constraint:
$$
T_{\text{total}} = (H_k + V_k)(H_s + V_s)
$$
Subtract overlapping configurations:
Let $ O $ be the number of pairs $(C_1, C_2)$ where the snakes overlap.
Overlap occurs only if:
- One is horizontal and the other vertical, and their rectangles intersect.
For Kiki horizontal and Susu vertical:
- Kiki occupies row $ i $, columns $ j $ to $ j+k-1 $.
- Susu occupies column $ j' $, rows $ i' $ to $ i'+s-1 $.
- They overlap iff $ i \in [i', i'+s-1] $ and $ j' \in [j, j+k-1] $.
Number of such overlapping pairs:
$$
O_{\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]}
$$
This simplifies to:
$$
O_{\text{hv}} = (n - s + 1)(m - k + 1)(s)(k)
$$
Similarly, for Kiki vertical and Susu horizontal:
$$
O_{\text{vh}} = (n - k + 1)(m - s + 1)(k)(s)
$$
Total overlapping pairs:
$$
O = O_{\text{hv}} + O_{\text{vh}} = ks \left[ (n - s + 1)(m - k + 1) + (n - k + 1)(m - s + 1) \right]
$$
Thus, the number of valid configurations is:
$$
\boxed{
\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
}
$$