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

Note

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

Permutation	Oddness
$$$[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$$$.

Permutation Oddness

Examples