102203: [AtCoder]ABC220 D - FG operation

Problem Statement

We have a sequence of $N$ integers between $0$ and $9$ (inclusive): $A=(A_1, \dots, A_N)$, arranged from left to right in this order.

Until the length of the sequence becomes $1$, we will repeatedly do the operation $F$ or $G$ below.

• Operation $F$: delete the leftmost two values (let us call them $x$ and $y$) and then insert $(x+y)\%10$ to the left end.
• Operation $G$: delete the leftmost two values (let us call them $x$ and $y$) and then insert $(x\times y)\%10$ to the left end.

Here, $a\%b$ denotes the remainder when $a$ is divided by $b$.

For each $K=0,1,\dots,9$, answer the following question.

Among the $2^{N-1}$ possible ways in which we do the operations, how many end up with $K$ being the final value of the sequence?
Since the answer can be enormous, find it modulo $998244353$.

Constraints

• $2 \leq N \leq 10^5$
• $0 \leq A_i \leq 9$
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

$N$
$A_1$ $\dots$ $A_N$

Output

Print ten lines.
The $i$-th line should contain the answer for the case $K=i-1$.

Sample Input 1

3
2 7 6

Sample Output 1

1
0
0
0
2
1
0
0
0
0

If we do Operation $F$ first and Operation $F$ second: the sequence becomes $(2,7,6)→(9,6)→(5)$.
If we do Operation $F$ first and Operation $G$ second: the sequence becomes $(2,7,6)→(9,6)→(4)$.
If we do Operation $G$ first and Operation $F$ second: the sequence becomes $(2,7,6)→(4,6)→(0)$.
If we do Operation $G$ first and Operation $G$ second: the sequence becomes $(2,7,6)→(4,6)→(4)$.

Sample Input 2

5
0 1 2 3 4

Sample Output 2

6
0
1
1
4
0
1
1
0
2

问题描述

我们有一个包含0到9（含）之间N个整数的序列：$A=(A_1, \dots, A_N)$，按从左到右的顺序排列。

我们反复执行以下操作$F$或$G$，直到序列长度变为1。

• 操作$F$：删除最左边的两个值（我们将其称为$x$和$y$），然后将$(x+y)\%10$插入到左边。
• 操作$G$：删除最左边的两个值（我们将其称为$x$和$y$），然后将$(x\times y)\%10$插入到左边。

这里，$a\%b$表示$a$除以$b$的余数。

对于每个$K=0,1,\dots,9$，回答以下问题。

在执行操作的所有$2^{N-1}$种可能方式中，有多少种方式最终序列的最后一个值为$K$？
由于答案可能非常大，请将其取模$998244353$。

约束

• $2 \leq N \leq 10^5$
• $0 \leq A_i \leq 9$
• 输入中的所有值都是整数。

输入

输入从标准输入中给出，格式如下：

$N$
$A_1$ $\dots$ $A_N$

输出

打印10行。
第$i$行应包含$K=i-1$时的答案。

样例输入1

3
2 7 6

样例输出1

1
0
0
0
2
1
0
0
0
0

如果我们首先执行操作$F$，然后执行操作$F$：序列变为$(2,7,6)→(9,6)→(5)$。
如果我们首先执行操作$F$，然后执行操作$G$：序列变为$(2,7,6)→(9,6)→(4)$。
如果我们首先执行操作$G$，然后执行操作$F$：序列变为$(2,7,6)→(4,6)→(0)$。
如果我们首先执行操作$G$，然后执行操作$G$：序列变为$(2,7,6)→(4,6)→(4)$。

样例输入2

5
0 1 2 3 4

样例输出2

6
0
1
1
4
0
1
1
0
2