모자 쓴 아이들 (Large)

계단에 아이 $k$명이 한 줄로 서 있다. 아이들은 각자 검은색 모자나 흰색 모자를 하나 쓰고 있다. 아이들은 계단 아래쪽만 볼 수 있어서 자기보다 아래에 서 있는 아이의 모자만 보이고, 자기 모자와 자기보다 위에 있는 아이의 모자는 보이지 않는다. 모든 아이는 검은색 모자의 전체 개수 $B$와 흰색 모자의 전체 개수 $W$를 알고 있다.

아이보다 모자가 많을 수 있고, 아무도 쓰지 않은 모자는 인솔자가 감추고 있다.

인솔자는 계단 맨 위에 있는 아이부터 아래로 차례차례 자기 모자 색을 아는지 물어봤다. 아이들은 모두 완벽하게 추론하고, 앞서 대답한 아이가 자기 모자 색을 모른다고 한 사실까지 근거로 쓴다. 그러다 한 아이가 자기 모자 색을 맞혔고, 그 아이보다 아래에 있는 아이에게는 더 묻지 않았다. 즉 맞힌 아이는 자기 모자 색을 처음으로 알아낸 아이다.

위 그림은 아이 3명에 검은색 모자와 흰색 모자가 각각 2개인 상황에서 뒤에서 두 번째 아이가 맞힌 경우다. 계단 맨 위에 있는 아이가 뒤에서 첫 번째 아이다.

• 맨 뒤에 있는 아이에게 보이는 것은 검은색 모자 하나와 흰색 모자 하나다. 아래의 두 아이가 모두 검은색을 썼다면 검은색 모자가 남지 않으니 자기 모자가 흰색임을 알았을 것이고, 둘 다 흰색을 썼다면 같은 이유로 검은색임을 알았을 것이다. 지금은 두 아이의 색이 달라서 자기 모자 색을 알 수 없다.
• 두 번째 아이는 자기 모자가 검은색이었다면 맨 뒤의 아이가 자기 모자를 흰색이라고 맞혔으리라는 것을 안다. 맨 뒤의 아이가 모른다고 했으니 자기 모자는 흰색이다.

당신은 이 이야기를 친구에게 전해 들었다. 친구는 상황을 정확히 기억하지 못하고, 아이 수 $k$, 검은색 모자 수 $B$, 흰색 모자 수 $W$, 그리고 뒤에서 몇 번째 아이가 맞혔는지를 뜻하는 $i$만 알려주었다. 이 정보에 맞는 경우가 몇 가지인지 세어라. 아이들이 쓴 모자 색을 계단 위에서 아래 순서로 늘어놓은 배열이 다르면 서로 다른 경우로 센다. 경우의 수가 매우 클 수 있으므로 $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 2000$

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