시간 제한메모리 제한제출정답맞힌 사람정답 비율
5 초 512 MB325350.000%

문제

계단에 그림과 같이 검은색 혹은 흰색 모자를 쓴 아이들이 서 있다. 아이들은 계단 아래쪽만 볼 수 있고 전체 검은색 모자와 흰색 모자의 개수를 각각 알고 있다. 아이들보다 모자가 많아서, 모자가 남을 수 있는데, 이 경우 아이들이 쓰고 있지 않은 모자는 인솔자가 감추고 있다. 인솔자는 계단 맨 위에 있는 아이부터 차례차례 자신이 쓰고 있는 모자의 색을 알 수 있는지 물어보았고, 한 아이가 정답을 맞혔다. (즉 자신이 쓰고 있는 모자의 색을 맞혔다.) 정답을 맞힌 아이가 나온 후에는 그 앞에 있는 아이들에게는 더 이상 물어보지 않았다.

위 그림은 3명의 아이가 검은색/흰색 모자가 각각 2개인 상황에 뒤에서부터 2번째 아이가 정답을 말한 경우이다.

  • 맨 뒤에 있는 아이가 볼 수 있는 것은, 검은색 모자 하나와 흰색 모자 하나이다. 만약 앞에 있는 아이가 둘 다 검은색의 모자를 쓰고 있었다면, 흰색 모자만 남기 때문에 자신이 흰색 모자를 쓰고 있다는 것을 알았을 것이다. 둘 다 흰색 모자를 쓰고 있을 때에도 자기 모자 색을 알 수 있었을 테지만 그렇지 않기 때문에 자신의 모자를 알 수 없다.
  • 두 번째 아이는 만일 자기 모자 색이 검은색이었다면 맨 뒤에 있는 아이가 자기 모자 색이 흰색인 것을 맞췄을 것이기 때문에 자기 모자 색이 흰색이라는 것을 알 수 있다.

 

당신은 이 상황에 대해 친구에게 전해 들었다. 친구는 상황이 정확히 어땠는지는 기억하지 못하고, 다만 아이들의 수와 검은색/흰색 모자의 수, 그리고 뒤에서 몇 번째 아이가 답을 맞혔는지만 알려주었다. 당신은 친구가 얘기해 준 정보에 맞는 경우의 수가 궁금해졌다. 이 경우의 수는 물론 매우 클 수 있기 때문에 32749로 나눈 나머지를 구하기로 한다.

입력

입력의 첫 줄에는 테스트 케이스의 숫자 T가 주어진다. 아래로 T 줄의 입력이 주어지며 각 줄은 하나의 테스트 케이스에 대한 입력이다. 각 테스트 케이스는 아래와 같이 4개의 자연수로 주어진다.

B W k i

여기에서 B와 W는 각각 검은색 모자와 흰색 모자의 수, k는 아이들의 수, 그리고 i는 뒤에서 몇 번째 아이가 맞췄는지를 나타낸다.

제한

  • 1 ≤ T ≤ 100.
  • 0 ≤ BW.
  • k ≤ B + W.
  • 1 ≤ i ≤ k.
  • BWk ≤ 20.

출력

각 테스트 케이스에 대한 출력은 "Case #x: y" 형태로 이루어져야 한다. x는 1부터 시작되는 케이스 번호이고, y는 주어진 조건에 맞는 경우의 수를 32749로 나눈 나머지이다.

예제 입력 1

3
2 2 3 2
2 4 6 1
0 7 5 1

예제 출력 1

Case #1: 4
Case #2: 15
Case #3: 1 

채점 및 기타 정보

  • 예제는 채점하지 않는다.