F. Permutation Oddness
time limit per test
5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given four positive integers $$$c_0$$$, $$$c_1$$$, $$$c_2$$$, and $$$c_3$$$.

Let $$$n = c_0 + c_1 + c_2 + c_3$$$. Consider an array $$$a$$$ of $$$n$$$ integers with $$$x$$$ ($$$0\le x\le 3$$$) appearing $$$c_x$$$ times. For any distinct permutation$$$^{\text{∗}}$$$ $$$b$$$ of the array $$$a$$$, define its oddness as$$$^{\text{†}}$$$$$$^{\text{‡}}$$$:

$$$$$$\sum_{i = 1}^{n-1} \text{lowbit}(b_i \oplus b_{i+1})$$$$$$

Your task is to count, for each integer $$$k$$$ from $$$0$$$ to $$$2 \cdot (n-1)$$$ (inclusive), the number of distinct permutations of $$$a$$$ with an oddness equal to $$$k$$$.

Since the numbers might be too large, you are only required to find them modulo $$$10^9 + 7$$$.

$$$^{\text{∗}}$$$A permutation of the array is an arrangement of its elements into any order. For example, $$$[1,2,2]$$$ is a permutation of $$$[2,2,1]$$$, but $$$[1,1,2]$$$ is not. Two permutations are considered distinct if they differ in at least one position.

$$$^{\text{†}}$$$$$$\oplus$$$ denotes the bitwise XOR operation.

$$$^{\text{‡}}$$$$$$\text{lowbit}(x)$$$ is the value of the lowest binary bit of $$$x$$$, e.g. $$$\text{lowbit}(12)=4$$$, $$$\text{lowbit}(8)=8$$$. Specifically, we define $$$\text{lowbit}(0) = 0$$$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 50$$$). The description of the test cases follows.

The first and the only line of each test case contains four positive integers $$$c_0$$$, $$$c_1$$$, $$$c_2$$$, and $$$c_3$$$ ($$$1 \le c_0, c_1, c_2, c_3 \lt 800$$$, $$$4 \le c_0 + c_1 + c_2 + c_3 \le 800$$$).

Let $$$n = c_0 + c_1 + c_2 + c_3$$$. It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$800$$$.

Output

For each test case, output $$$2 \cdot (n-1) + 1$$$ integers in one line — the number of distinct permutations of $$$a$$$ with an oddness equal to $$$0,1,\ldots, 2 \cdot (n-1)$$$ respectively. Output the answers modulo $$$10^9+7$$$.

Example
Input
3
1 1 1 1
1 2 4 1
3 3 3 3
Output
0 0 0 8 8 8 0
0 0 0 8 32 126 184 244 156 72 18 0 0 0 0
0 0 0 8 56 424 1472 5760 12128 29376 40384 65232 59920 65232 40384 29376 12128 5760 1472 424 56 8 0
Note

In the first test case, the array $$$a$$$ has $$$24$$$ distinct permutations. The table below shows the oddness values for some selected permutations:

PermutationOddness
$$$[0,1,2,3]$$$$$$\text{lowbit}(0 \oplus 1) + \text{lowbit}(1 \oplus 2) + \text{lowbit}(2 \oplus 3) = 1 + 1 + 1 = 3$$$
$$$[0,2,1,3]$$$$$$\text{lowbit}(0 \oplus 2) + \text{lowbit}(2 \oplus 1) + \text{lowbit}(1 \oplus 3) = 2 + 1 + 2 = 5$$$
$$$[0,1,3,2]$$$$$$\text{lowbit}(0 \oplus 1) + \text{lowbit}(1 \oplus 3) + \text{lowbit}(3 \oplus 2) = 1 + 2 + 1 = 4$$$

Overall, among the $$$24$$$ permutations:

  • $$$8$$$ permutations have oddness $$$3$$$.
  • $$$8$$$ permutations have oddness $$$4$$$.
  • $$$8$$$ permutations have oddness $$$5$$$.

In the second test case, the array $$$a$$$ has $$$840$$$ distinct permutations. The distribution of oddness values is as follows:

  • $$$8$$$ permutations have oddness $$$3$$$.
  • $$$32$$$ permutations have oddness $$$4$$$.
  • $$$126$$$ permutations have oddness $$$5$$$.
  • $$$184$$$ permutations have oddness $$$6$$$.
  • $$$244$$$ permutations have oddness $$$7$$$.
  • $$$156$$$ permutations have oddness $$$8$$$.
  • $$$72$$$ permutations have oddness $$$9$$$.
  • $$$18$$$ permutations have oddness $$$10$$$.