给定四个正整数 $$$c_0$$$、$$$c_1$$$、$$$c_2$$$ 和 $$$c_3$$$。
设$$$n = c_0 + c_1 + c_2 + c_3$$$。考虑一个由 $$$n$$$ 整数组成的数组 $$$a$$$,其中 $$$x$$$ ($$$0\le x\le 3$$$) 出现 $$$c_x$$$ 次。对于任何 不同的排列$$$^{\text{*}}$$$ $$$b$$$ 的数组$$$a$$$,定义其 奇怪 as$$$^{\text{†}}$$$$$$^{\text{‡}}$$$:
$$\sum_{i = 1}^{n-1} \text{lowbit}(b_i \oplus b_{i+1})$$
你的任务是,对于从 $$$0$$$ 到 $$$2 \cdot (n-1)$$$(含)的每个整数 $$$k$$$,计算奇数等于 $$$k$$$ 的 $$$a$$$ 的不同排列的数量。
由于数字可能太大,您只需对 $$$10^9 + 7$$$ 求模即可。
$$$^{\text{*}}$$$数组的排列是将其元素排列成任意顺序。例如,$$$[1,2,2]$$$ 是 $$$[2,2,1]$$$ 的排列,但 $$$[1,1,2]$$$ 不是。如果两个排列至少在一个位置不同,则认为它们是不同的。
$$$^{\text{†}}$$$$$$\oplus$$$ 表示按位异或运算。
$$$^{\text{‡}}$$$$$$\text{lowbit}(x)$$$ 是 $$$x$$$ 的最低二进制位的值,例如$$$\text{lowbit}(12)=4$$$,$$$\text{lowbit}(8)=8$$$。具体来说,我们定义$$$\text{lowbit}(0) = 0$$$。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 50$$$)。测试用例的描述如下。
每个测试用例的第一行也是唯一一行包含四个正整数 $$$c_0$$$、$$$c_1$$$、$$$c_2$$$ 和 $$$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$$$)。
设$$$n = c_0 + c_1 + c_2 + c_3$$$。保证所有测试用例的 $$$n$$$ 总和不超过 $$$800$$$。
输出
对于每个测试用例,在一行中输出 $$$2 \cdot (n-1) + 1$$$ 整数 - $$$a$$$ 的不同排列的数量,奇数分别等于 $$$0,1,\ldots, 2 \cdot (n-1)$$$。输出对 $$$10^9+7$$$ 取模的答案。
示例
输入复制
31 1 1 11 2 4 13 3 3 3
输出复制
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
注意
在第一个测试用例中,数组 $$$a$$$ 具有 $$$24$$$ 不同的排列。下表显示了一些选定排列的奇数值:
| 排列 | 奇怪 |
| $$$[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$$$ |
总体而言,在 $$$24$$$ 排列中:
- $$$8$$$ 排列具有奇数 $$$3$$$。
- $$$8$$$ 排列具有奇数 $$$4$$$。
- $$$8$$$ 排列具有奇数 $$$5$$$。
在第二个测试用例中,数组 $$$a$$$ 具有 $$$840$$$ 不同的排列。奇数值的分布如下:
- $$$8$$$ 排列具有奇数 $$$3$$$。
- $$$32$$$ 排列具有奇数 $$$4$$$。
- $$$126$$$ 排列具有奇数 $$$5$$$。
- $$$184$$$ 排列具有奇数 $$$6$$$。
- $$$244$$$ 排列具有奇数 $$$7$$$。
- $$$156$$$ 排列具有奇数 $$$8$$$。
- $$$72$$$ 排列具有奇数 $$$9$$$。
- $$$18$$$ 排列具有奇数 $$$10$$$。