CF2134F Permutation Oddness

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

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

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

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