F. Permutation Oddnesstime limit per test5 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard 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$$$.InputEach 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 < 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$$$. OutputFor 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$$$.ExampleInput31 1 1 11 2 4 13 3 3 3Output0 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
NoteIn 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$$$.