310260: CF1806D. DSU Master

D. DSU Mastertime limit per test2 secondsmemory limit per test1024 megabytesinputstandard inputoutputstandard output

You are given an integer $n$ and an array $a$ of length $n-1$ whose elements are either $0$ or $1$.

Let us define the value of a permutation$^\dagger$ $p$ of length $m-1$ ($m \leq n$) by the following process.

Let $G$ be a graph of $m$ vertices labeled from $1$ to $m$ that does not contain any edges. For each $i$ from $1$ to $m-1$, perform the following operations:

• define $u$ and $v$ as the (unique) vertices in the weakly connected components$^\ddagger$ containing vertices $p_i$ and $p_i+1$ respectively with only incoming edges$^{\dagger\dagger}$;
• in graph $G$, add a directed edge from vertex $v$ to $u$ if $a_{p_i}=0$, otherwise add a directed edge from vertex $u$ to $v$ (if $a_{p_i}=1$).

Note that after each step, it can be proven that each weakly connected component of $G$ has a unique vertex with only incoming edges.

Then, the value of $p$ is the number of incoming edges of vertex $1$ of $G$.

For each $k$ from $1$ to $n-1$, find the sum of values of all $k!$ permutations of length $k$. Since this value can be big, you are only required to compute this value under modulo $998\,244\,353$.

Operations when $n=3$, $a=[0,1]$ and $p=[1,2]$

$^\dagger$ A permutation of length $n$ is an array consisting of $n$ distinct integers from $1$ to $n$ in arbitrary order. For example, $[2,3,1,5,4]$ is a permutation, but $[1,2,2]$ is not a permutation ($2$ appears twice in the array), and $[1,3,4]$ is also not a permutation ($n=3$ but there is $4$ in the array).

$^\ddagger$ The weakly connected components of a directed graph is the same as the components of the undirected version of the graph. Formally, for directed graph $G$, define a graph $H$ where for all edges $a \to b$ in $G$, you add an undirected edge $a \leftrightarrow b$ in $H$. Then the weakly connected components of $G$ are the components of $H$.

$^{\dagger\dagger}$ Note that a vertex that has no edges is considered to have only incoming edges.

Input

The first line contains a single integer $t$ ($1\le t\le 10^4$) — the number of test cases. The description of test cases follows.

The first line of each test case contains a single integer $n$ ($2\le n\le 5 \cdot 10^5$).

The second line of each test case contains $n-1$ integers $a_1, a_2, \ldots, a_{n-1}$ ($a_i$ is $0$ or $1$).

It is guaranteed that the sum of $n$ over all test cases does not exceed $5 \cdot 10^5$.

Output

For each test case, output $n-1$ integers in a line, the $i$-th integer should represent the answer when $k=i$, under modulo $998\,244\,353$.

ExampleInput

2
3
0 0
9
0 1 0 0 0 1 0 0

Output

1 3 
1 2 7 31 167 1002 7314 60612 

Note

Consider the first test case.

When $k=1$, there is only $1$ permutation $p$.

• When $p=[1]$, we will add a single edge from vertex $2$ to $1$. Vertex $1$ will have $1$ incoming edge. So the value of $[1]$ is $1$.

Therefore when $k=1$, the answer is $1$.

When $k=2$, there are $2$ permutations $p$.

• When $p=[1,2]$, we will add an edge from vertex $2$ to $1$ and an edge from $3$ to $1$. Vertex $1$ will have $2$ incoming edges. So the value of $[1,2]$ is $2$.
• When $p=[2,1]$, we will add an edge from vertex $3$ to $2$ and an edge from $2$ to $1$. Vertex $1$ will have $1$ incoming edge. So the value of $[2,1]$ is $1$.

Therefore when $k=2$, the answer is $2+1=3$.

题目大意：

给定一个整数 $ n $ 和一个长度为 $ n-1 $ 的数组 $ a $，数组元素为 $ 0 $ 或 $ 1 $。

定义一个长度为 $ m-1 $ ($ m \leq n $) 的排列 $ p $ 的 **值** 如下：

1. 设 $ G $ 为一个有 $ m $ 个顶点（从 $ 1 $ 到 $ m $ 标记）的无边图。
2. 对于每个 $ i $ 从 $ 1 $ 到 $ m-1 $，执行以下操作：
- 定义 $ u $ 和 $ v $ 为弱连通分量中只含有入边的唯一顶点，分别包含顶点 $ p_i $ 和 $ p_i+1 $；
- 如果 $ a_{p_i}=0 $，在图 $ G $ 中从顶点 $ v $ 到 $ u $ 添加一条有向边；如果 $ a_{p_i}=1 $，则从顶点 $ u $ 到 $ v $ 添加一条有向边。
3. 注意，在每一步之后，可以证明 $ G $ 的每个弱连通分量都有一个唯一顶点，该顶点只有入边。

排列 $ p $ 的值是图 $ G $ 中顶点 $ 1 $ 的入边数。

对于每个 $ k $ 从 $ 1 $ 到 $ n-1 $，找到所有 $ k! $ 长度为 $ k $ 的排列的值的和。由于这个值可能很大，你只需要在模 $ 998,244,353 $ 下计算这个值。

输入输出数据格式：

输入：

- 第一行包含一个整数 $ t $ ($ 1 \leq t \leq 10^4 $) —— 测试用例的数量。
- 每个测试用例的描述如下：
- 第一行包含一个整数 $ n $ ($ 2 \leq n \leq 5 \times 10^5 $)。
- 第二行包含 $ n-1 $ 个整数 $ a_1, a_2, \ldots, a_{n-1} $ ($ a_i $ 为 $ 0 $ 或 $ 1 $)。
- 保证所有测试用例的 $ n $ 之和不超过 $ 5 \times 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
```题目大意： 给定一个整数 $ n $ 和一个长度为 $ n-1 $ 的数组 $ a $，数组元素为 $ 0 $ 或 $ 1 $。 定义一个长度为 $ m-1 $ ($ m \leq n $) 的排列 $ p $ 的 **值** 如下： 1. 设 $ G $ 为一个有 $ m $ 个顶点（从 $ 1 $ 到 $ m $ 标记）的无边图。 2. 对于每个 $ i $ 从 $ 1 $ 到 $ m-1 $，执行以下操作： - 定义 $ u $ 和 $ v $ 为弱连通分量中只含有入边的唯一顶点，分别包含顶点 $ p_i $ 和 $ p_i+1 $； - 如果 $ a_{p_i}=0 $，在图 $ G $ 中从顶点 $ v $ 到 $ u $ 添加一条有向边；如果 $ a_{p_i}=1 $，则从顶点 $ u $ 到 $ v $ 添加一条有向边。 3. 注意，在每一步之后，可以证明 $ G $ 的每个弱连通分量都有一个唯一顶点，该顶点只有入边。 排列 $ p $ 的值是图 $ G $ 中顶点 $ 1 $ 的入边数。 对于每个 $ k $ 从 $ 1 $ 到 $ n-1 $，找到所有 $ k! $ 长度为 $ k $ 的排列的值的和。由于这个值可能很大，你只需要在模 $ 998,244,353 $ 下计算这个值。 输入输出数据格式： 输入： - 第一行包含一个整数 $ t $ ($ 1 \leq t \leq 10^4 $) —— 测试用例的数量。 - 每个测试用例的描述如下： - 第一行包含一个整数 $ n $ ($ 2 \leq n \leq 5 \times 10^5 $)。 - 第二行包含 $ n-1 $ 个整数 $ a_1, a_2, \ldots, a_{n-1} $ ($ a_i $ 为 $ 0 $ 或 $ 1 $)。 - 保证所有测试用例的 $ n $ 之和不超过 $ 5 \times 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 ```