FG 操作

题目描述

我们有一个长度为 $N$ 的序列 $A=(A_1, \dots, A_N)$，每个元素都是 $0$ 到 $9$ 之间（含两端）的整数，按从左到右的顺序排列。

在序列长度变为 $1$ 之前，我们重复执行下面的操作 $F$ 或操作 $G$。

操作 $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$ 对应的答案。

样例

3
2 7 6

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)$。

5
0 1 2 3 4

6
0
1
1
4
0
1
1
0
2

数据范围

• $2 \le N \le 10^5$
• $0 \le A_i \le 9$
• 输入均为整数