F. Нечётность перестановки
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Даны четыре целых положительных числа $$$c_0$$$, $$$c_1$$$, $$$c_2$$$ и $$$c_3$$$.

Обозначим $$$n = c_0 + c_1 + c_2 + c_3$$$. Рассмотрим массив $$$a$$$ из $$$n$$$ целых чисел, где $$$x$$$ ($$$0\le x\le 3$$$) встречается $$$c_x$$$ раз. Для любой уникальной перестановки$$$^{\text{∗}}$$$ $$$b$$$ массива $$$a$$$ определим её нечетность как$$$^{\text{†}}$$$$$$^{\text{‡}}$$$:

$$$$$$\sum_{i = 1}^{n-1} \text{lowbit}(b_i \oplus b_{i+1})$$$$$$

Ваша задача — подсчитать для каждого целого числа $$$k$$$ от $$$0$$$ до $$$2 \cdot (n-1)$$$ (включительно), количество различных перестановок массива $$$a$$$ с нечетностью, равной $$$k$$$.

Поскольку числа могут быть слишком большими, вам нужно найти их только по модулю $$$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$$$.

Пример
Входные данные
3
1 1 1 1
1 2 4 1
3 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$$$.