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](https://en.wikipedia.org/wiki/Bitwise_operation#XOR). $^{\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:

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