Children Wearing Hats (Small)

Children stand in one line on a staircase. Each child wears one black hat or one white hat and can see only the children standing lower on the stairs. Every child knows the total number of black hats and the total number of white hats. There can be more hats than children, and the leader keeps the hats that nobody wears hidden.

The leader started with the child at the top of the stairs and worked downward, asking each child in turn whether they know the color of their own hat. The children reason without error, and each of them hears every answer given before their turn. One child named the color of their own hat correctly, so the leader stopped and asked nobody below that child.

The picture shows 3 children with 2 black hats and 2 white hats, where the second child from the back answered. The back of the line is the top of the stairs.

• The child at the back sees one black hat and one white hat. Had both children below worn black, only white hats would be left and that child would know their own color, and the same holds if both below wore white. One hat of each color is visible, so that child cannot tell.
• The second child knows that a black hat on their own head would have let the child at the back answer. The child at the back said no, so the second child wears white.

A friend told you about this. The friend remembers only the number of children, the number of black hats and white hats, and which child from the back answered. Count the hat arrangements that fit what the friend told you. An arrangement fixes the color worn by each child, and hats of the same color are not distinguished. The count can be very large, so report it modulo 32749.

The first line has the number of test cases $T$. Each of the next $T$ lines holds one test case as four integers separated by spaces.

B W k i

$B$ is the number of black hats, $W$ is the number of white hats, $k$ is the number of children, and $i$ tells which child from the back answered.

Limits

• $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$

For each test case, print one line in the form Case #x: y, where $x$ is the test case number starting from 1 and $y$ is the number of matching arrangements modulo 32749.