题目描述

小高有一个长度为 $N$ 的整数序列 $A=(A_1,\dots,A_N)$ ，其中每个元素都在 0 到 9 之间（包括 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$ 取模。

输入格式

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

$N$

$A_1$ $\dots$ $A_N$

输出格式

输出十行。

第 $i$ 行应包含 $K = i−1$时的答案。

输入输出样例 #1

输入 #1

3
2 7 6

输出 #1

1
0
0
0
2
1
0
0
0
0

输入输出样例 #2

输入 #2

5
0 1 2 3 4

输出 #2

6
0
1
1
4
0
1
1
0
2

说明/提示

样例 1 解释

如果先做操作 $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\ \leq\ N\ \leq\ 10^5$
• $0\ \leq\ A_i\ \leq\ 9$
• 所有输入都是整数。