题目描述

小高有一个长度为 $N$ 的整数序列 $A=(A_1, \cdots, A_N)$，其中每个元素都在 0 到 9 之间（包括 0 和 9）。他将重复执行以下操作，直到序列长度变为 1：

• 操作 $F$：删除最左边的两个值（设为 $x$ 和 $y$），然后在左端插入 $(x+y)$。
• 操作 $G$：删除最左边的两个值（设为 $x$ 和 $y$），然后在左端插入 $(x\times y)$。

这里，$a$ 表示 $a$ 除以 $b$ 的余数。对于每个 $K=0,1,\dots,9$，请回答以下问题：在 $2^{N-1}$ 种可能的操作方式中，有多少种最终会得到值为 $K$ 的序列？由于答案可能非常大，请对 998244353 取模。

输入格式

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

$N$

$A_1$ ... $A_N$

输出格式

输出十行。第 $i$ 行应包含 $K=i-1$ 时的答案。

样例

3
2 7 6

1
0
0
0
2
1
0
0
0
0

5
0 1 2 3 4

6
0
1
1
4
0
1
1
0
2

数据范围

如果先做操作 $F$ 再做操作 $F$：序列变化为 $(2,7,6)\rightarrow(9,6)\rightarrow(5)$。
如果先做操作 $F$ 再做操作 $G$：序列变化为 $(2,7,6)\rightarrow(9,6)\rightarrow(4)$。
如果先做操作 $G$ 再做操作 $F$：序列变化为 $(2,7,6)\rightarrow(4,6)\rightarrow(0)$。
如果先做操作 $G$ 再做操作 $G$：序列变化为 $(2,7,6)\rightarrow(4,6)\rightarrow(4)$。

数据范围

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

来源

• AtCoder ABC220D