题目描述

我们有一个由 $N$ 个整数组成的序列 $A=(A_1, \\dots, A_N)$，每个整数都在 $0$ 到 $9$ 之间（包括边界），按照从左到右的顺序排列。

直到序列的长度变为 $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$

输出

打印十行。
第 $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