모자 쓴 아이들 (Small)

계단에 아이들이 한 줄로 서 있다. 각 아이는 검은색 모자나 흰색 모자를 하나 쓰고 있고, 자기보다 계단 아래에 있는 아이만 볼 수 있다. 아이들은 모두 검은색 모자와 흰색 모자의 전체 개수를 알고 있다. 모자가 아이보다 많을 수 있는데, 아무도 쓰지 않은 모자는 인솔자가 감추고 있다.

인솔자는 계단 맨 위에 있는 아이부터 아래로 내려오며 자기 모자의 색을 아는지 차례로 물었다. 아이들은 빈틈없이 추론하고, 앞서 나온 대답을 모두 듣는다. 한 아이가 자기 모자의 색을 맞히자 인솔자는 질문을 멈췄고, 그보다 아래에 있는 아이에게는 묻지 않았다.

위 그림은 아이가 3명이고 검은색 모자와 흰색 모자가 각각 2개일 때, 뒤에서 두 번째 아이가 답을 맞힌 경우이다. 여기서 맨 뒤는 계단 맨 위를 뜻한다.

• 맨 뒤 아이에게는 검은색 모자 하나와 흰색 모자 하나가 보인다. 아래 두 아이가 모두 검은색 모자를 썼다면 남는 모자가 흰색뿐이므로 자기 모자의 색을 알았을 것이고, 둘 다 흰색이었어도 마찬가지다. 지금은 색이 하나씩 보이므로 자기 모자의 색을 알 수 없다.
• 두 번째 아이는 자기 모자가 검은색이라면 맨 뒤 아이가 답을 맞혔으리라는 것을 안다. 맨 뒤 아이가 모른다고 했으니 자기 모자는 흰색이다.

당신은 이 상황을 친구에게 전해 들었다. 친구는 아이의 수, 검은색 모자와 흰색 모자의 수, 뒤에서 몇 번째 아이가 답을 맞혔는지만 기억한다. 친구가 말해 준 정보와 들어맞는 모자 배치가 몇 가지인지 세어라. 아이마다 쓴 모자의 색을 정한 것이 배치 하나이고, 같은 색 모자끼리는 구별하지 않는다. 경우의 수가 매우 클 수 있으므로 32749로 나눈 나머지를 구한다.

첫 줄에 테스트 케이스의 수 $T$가 주어진다. 다음 $T$개의 줄에 테스트 케이스가 한 줄씩 주어지고, 각 줄에는 정수 네 개가 공백으로 구분되어 주어진다.

B W k i

$B$는 검은색 모자의 수, $W$는 흰색 모자의 수, $k$는 아이의 수, $i$는 뒤에서 몇 번째 아이가 답을 맞혔는지를 나타낸다.

제한

• $1 \le T \le 100$
• $0 \le B$, $0 \le W$
• $k \le B + W$
• $1 \le i \le k$
• $B, W, k \le 20$

각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. $x$는 1부터 시작하는 테스트 케이스 번호이고, $y$는 조건에 맞는 경우의 수를 32749로 나눈 나머지이다.