403127: GYM101020 K Clash Of Snakes

K. Clash Of Snakestime limit per test2 secondsmemory limit per test64 megabytesinputstandard inputoutputstandard output

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):

Kiki and Susu are very confused and they don't 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's head is at (x₁, y₁) and its tail is at (x₂, y₂) is considered different from the case in which the snake's head is at (x₂, y₂) and its tail is at (x₁, y₁). 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.

ExamplesInput

4
2 2 2 2
3 3 3 3
2 3 2 2
4 4 3 2

Output

Case 1: 16
Case 2: 48
Case 3: 88
Case 4: 1056