Children Wearing Hats (Large)

$k$ children stand in a line on a staircase. Each child wears one hat, black or white. A child can only look down the staircase, so a child sees the hats of the children standing below and never sees their own hat or the hats of the children above. Every child knows the total number of black hats $B$ and the total number of white hats $W$.

There can be more hats than children. The leader keeps every unworn hat hidden.

The leader starts with the child at the top of the staircase and asks each child in turn, going down, whether they know the colour of their own hat. Every child reasons perfectly and also uses the fact that each earlier child said they did not know. Then one child named their own colour correctly, and the children below that child were not asked. So the child who answered is the first child able to deduce their own hat colour.

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

• The child at the back sees one black hat and one white hat. If both children below wore black, no black hat would be left, so that child would know their own hat is white. If both wore white, the same argument gives black. Here the two colours differ, so the child at the back cannot tell.
• The second child knows that a black hat on their own head would have let the child at the back name white. The child at the back said they did not know, so the second child's hat is white.

A friend told you about this. The friend does not remember the exact situation and gave you only the number of children $k$, the number of black hats $B$, the number of white hats $W$, and the position $i$ of the answering child counted from the back. Count how many cases match that information. Two cases are different when the sequence of hat colours, read from the top of the staircase down, differs. 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.

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.

Constraints

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

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