问题描述

在遥远的小镇，住着一位名叫阿莉亚的神奇玩具匠，她擅长用数字和魔法制作玩具。一天，圣诞老人向她提出了一个有趣的挑战。这个挑战需要她用玩具工坊中的数字魔法来完成一系列操作，最终计算出可能的结果。

阿莉亚的工坊有一个特殊的数字序列：

其中每个数字代表某种魔法玩具的能量等级，范围是 $0$ 到 $9$。圣诞老人的挑战是通过以下两种操作逐步将这个数字序列缩减为一个数字，操作次数为 $N-1$ 次。每次操作可以选择以下之一：

• 操作 X：从玩具工坊中取出最左边的两个玩具能量等级 $x$ 和 $y$，将它们合并为新的玩具，能量等级为 $(x + y) \mod 10$，然后将其放回最左边。
• 操作 Y：从玩具工坊中取出最左边的两个玩具能量等级 $x$ 和 $y$，将它们合并为新的玩具，能量等级为 $(x \times y) \mod 10$，然后将其放回最左边。

阿莉亚需要计算，对于每个数字 $k$（从 $0$ 到 $9$），通过魔法操作最终得到 $k$ 的不同方式有多少种。由于结果可能非常大，请对 $998244353$ 取模。

输入

第一行输入一个整数 $N$，表示玩具能量数组 $A$ 的长度。

第二行输入 $N$ 个正整数 $A_1, A_2, \dots, A_N$，表示玩具能量数组的初始状态，每个数字在 $0$ 到 $9$ 范围内。

输出

输出 $10$ 行，每行输出一个数值，表示通过操作最终结果为每个数字（从 $0$ 到 $9$）的不同方式数。

示例

4
2 3 7 6

1
1
2
0
0
0
0
0
3
1

数据范围

• $2 \leq N \leq 10^5$
• $0 \leq A_i \leq 9$