시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 7 4 4 57.143%

문제

두 마리의 사랑스러운 뱀 Kiki와 Susu는 n*m 직사각형 격자 위에서 노는 것을 좋아한다. 게임이 진행되는 동안에는 이들은 마구 뒤섞여 규칙을 신경쓰지 않지만, 게임을 시작할 때는 다음과 같은 규칙을 따른다.

  1. 두 뱀은 각각 한쪽 변의 길이가 1인 직사각형으로 나타낼 수 있다.
  2. 각 뱀들은 수평, 혹은 수직 방향으로 나열된다.
  3. 두 뱀 모두 격자판 안에 완전히 들어 있어야 한다.
  4. 두 뱀이 겹치는 칸이 있어서는 안 된다.

아래의 그림은 올바른 배치와 잘못된 배치를 보여준다. 위의 두 가지가 올바른 배치, 아래의 두 가지가 잘못된 배치에 해당한다. (격자판은 5*5이며, 두 뱀의 길이는 각각 3, 3이다.)

Kiki와 Susu는 게임을 시작할 수 있는 경우의 수가 몇 가지나 되는지 알고 싶어한다. 격자판의 크기가 n*m이고, Kiki의 길이와 Susu의 길이가 각각 k, s일 때, 두 뱀이 배치될 수 있는 경우의 수를 구하는 것을 도와주자.

주의 : 한 뱀의 머리가 (x1, y1), 뱀의 꼬리가 (x2, y2)에 있는 경우와, 뱀의 꼬리가 (x1,y1), 뱀의 머리가 (x2, y2)에 있는 경우는 서로 다른 경우로 생각한다. 즉, 머리의 방향을 고려해야 한다.

입력

각 Test Case는 한 줄의 입력으로 구성되어 있다. 한 Test Case에는 격자의 크기를 나타내는 n, m과 두 뱀의 길이를 나타내는 k, s가 주어진다. (2 ≤ n, m ≤ 100,000; 2 ≤ k, s ≤ min(n, m))

출력

각 Test case에 대해, “Case c: x”의 형식으로 각 줄에 정답을 출력한다. c는 Test Case의 번호 (1부터 매겨진다.), x는 문제의 정답을 1,000,000,007(109+7)로 나눈 나머지이다. 

예제 입력 1

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

예제 출력 1

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