D. Мастер СНМ
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Вам дано целое число $$$n$$$ и массив $$$a$$$ длины $$$n-1$$$, элементы которого либо $$$0$$$, либо $$$1$$$.

Определим стоимость перестановки $$$^\dagger$$$ $$$p$$$ длины $$$m-1$$$ ($$$m \leq n$$$) следующим образом.

Пусть $$$G$$$ - граф из $$$m$$$ вершин с номерами от $$$1$$$ до $$$m$$$, не содержащий ребер. Для каждого $$$i$$$ от $$$1$$$ до $$$m-1$$$ выполните следующие операции:

  • определим $$$u$$$ и $$$v$$$ как (различные) вершины с только входящими ребрами$$$^{\dagger\dagger}$$$ в компонентах слабой связности $$$^\ddagger$$$, содержащих вершины $$$p_i$$$ и $$$p_i+1$$$ соответственно
  • в графе $$$G$$$, добавим направленное ребро из вершины $$$v$$$ в $$$u$$$, если $$$a_{p_i}=0$$$, иначе добавим направленное ребро из вершины $$$u$$$ в $$$v$$$ (если $$$a_{p_i}=1$$$).
Заметим, что после каждого шага можно показать, что каждая компонента слабой связности $$$G$$$ имеет ровно одну вершину с только входящими рёбрами.

Тогда, значение $$$p$$$ — это количество входящих ребер $$$G$$$ в вершину $$$1$$$.

Для каждого $$$k$$$ от $$$1$$$ до $$$n-1$$$ найдите сумму стоимостей всех $$$k!$$$ перестановок длины $$$k$$$. Поскольку эта величина может быть большой, от вас требуется вычислить ее только по модулю $$$998\,244\,353$$$.

Операции при $$$n=3$$$, $$$a=[0,1]$$$ и $$$p=[1,2]$$$

$$$^\dagger$$$ Перестановка длины $$$n$$$ - это массив, состоящий из $$$n$$$ различных целых чисел от $$$1$$$ до $$$n$$$ в произвольном порядке. Например, $$$[2,3,1,5,4]$$$ - перестановка, но $$$[1,2,2]$$$ - не перестановка ($$$2$$$ встречается в массиве дважды), и $$$[1,3,4]$$$ - тоже не перестановка ($$$n=3$$$, но в массиве есть $$$4$$$).

$$$^\ddagger$$$ Компоненты слабой связности направленного графа — это то же самое, что и компоненты неориентированной версии графа. Формально, для направленного графа $$$G$$$ определите граф $$$H$$$, где для всех ребер $$$a \to b$$$ в $$$G$$$ добавляется неориентированное ребро $$$a \leftrightarrow b$$$ в $$$H$$$. Тогда компоненты слабой связности $$$G$$$ являются компонентами $$$H$$$.

$$$^{\dagger\dagger}$$$ Заметим, что вершина, не имеющая ребер, считается имеющей только входящие ребра.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1\le t\le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит одно число $$$n$$$ ($$$2\le n\le 5 \cdot 10^5$$$).

Вторая строка содержит $$$n-1$$$ чисел $$$a_1, a_2, \ldots, a_{n-1}$$$ ($$$a_i$$$ равно $$$0$$$ или $$$1$$$).

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$5 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите $$$n-1$$$ целых чисел в строке. $$$i$$$-е число является ответом для $$$k=i$$$, по модулю $$$998\,244\,353$$$.

Пример
Входные данные
2
3
0 0
9
0 1 0 0 0 1 0 0
Выходные данные
1 3 
1 2 7 31 167 1002 7314 60612
Примечание

Рассмотрим первый набор входных данных.

Когда $$$k=1$$$, существует только $$$1$$$ перестановка $$$p$$$.

  • Когда $$$p=[1]$$$, мы добавим одно ребро из вершины $$$2$$$ в $$$1$$$. Вершина $$$1$$$ будет иметь $$$1$$$ входящее ребро. Поэтому значение $$$[1]$$$ равно $$$1$$$.

Поэтому, когда $$$k=1$$$, ответ равен $$$1$$$.

Когда $$$k=2$$$, существует $$$2$$$ перестановки $$$p$$$.

  • Когда $$$p=[1,2]$$$, мы добавим ребро из вершины $$$2$$$ в $$$1$$$ и ребро из $$$3$$$ в $$$1$$$. Вершина $$$1$$$ будет иметь $$$2$$$ входящих ребер. Таким образом, значение $$$[1,2]$$$ равно $$$2$$$.
  • Когда $$$p=[2,1]$$$, мы добавим ребро из вершины $$$3$$$ в $$$2$$$ и ребро из $$$2$$$ в $$$1$$$. Вершина $$$1$$$ будет иметь входящее ребро $$$1$$$. Таким образом, значение $$$[2,1]$$$ равно $$$1$$$.

Поэтому, когда $$$k=2$$$, ответ будет $$$2+1=3$$$.