Mysterious SS Expression Counting

In A.D. 11380 a huge meteorite struck Antarctica and unleashed a series of bizarre phenomena. A team of Chinese scientists discovered that the meteorite was engraved with several lines of secret codes. Each line contains 5 integers. The first four integers, L₁, L₂, L₃ and D, represent parameters for a mysterious operation on a special kind of expression called an SS expression.

An SS expression is a string composed only of the characters {, }, [, ], (, ) defined by the following rules:

1. An empty string is an SS expression.
2. If A is an SS expression that does not contain { or }, then (A) is an SS expression.
3. If A is an SS expression that does not contain { or }, then [A] is an SS expression.
4. If A is an SS expression, then {A} is an SS expression.
5. If A and B are SS expressions, then their concatenation AB is also an SS expression.

The depth D(E) of an SS expression E is defined recursively as follows:

$$D(E)=\begin{cases} 0, & \text{if } E \text{ is empty},\\ D(A)+1, & \text{if } E=(A)\; \text{or}\; E=[A]\; \text{or}\; E=\{A\},\\ \max(D(A),D(B)), & \text{if } E=AB \text{ with } A, B \text{ SS expressions}. \end{cases} $$

For example, the expression (){()}[] has depth 2.

The secret operation is as follows: Given parameters L₁ (the number of {} pairs), L₂ (the number of [] pairs), L₃ (the number of () pairs), and a depth D, compute the number of SS expressions E that have exactly depth D and contain exactly L₁ pairs of {}, L₂ pairs of [] and L₃ pairs of ().

Finally, take the computed number modulo 11380; the result is the mysterious number hidden in the code.

You are given several test cases. For each test case, the input consists of 4 integers: L₁, L₂, L₃, and D. Output the mysterious number computed as described above.

inputFormat

The first line contains an integer T (T ≥ 1) that denotes the number of test cases. Each of the following T lines contains four non‐negative integers L₁, L₂, L₃, and D separated by spaces. It is guaranteed that the total number of bracket pairs (L₁ + L₂ + L₃) is small.

outputFormat

For each test case, output a single integer: the mysterious number (i.e. the count of valid SS expressions with exactly the given numbers of {} , [] and () pairs and exactly depth D, modulo 11380).

sample

3
1 1 1 1
0 0 0 0
1 0 1 2

6
1
1

</p>