题目描述

给你一个 $n$ 个整数的序列 $A$，序列的每个数字 $A_i(0 \le A_i \le 9)$ 。对于这个序列，有两种操作：

• 加操作：设最左边的两个元素为 $x,y$ ，把 $x,y$ 从序列中删除，然后在序列最左边插入 $(x+y)\%10$ 。
• 乘操作：设最左边的两个元素为 $x,y$ ，把 $x,y$ 从序列中删除，然后在序列最左边插入 $(x \times y)\%10$ 。

现在每次从两种操作种选一种对序列进行变化，重复多次，直到序列长度变为 $1$ 。因为每次有两种操作可以选择，所以让序列长度变为 $1$ 所有可能的操作序列有 $2^n-1$ 种，问在这 $2^n-1$ 种操作序列中，最后剩下的数字为 $0,1,2,3,4,...,9$ 的情况数分别有多少种，答案对 $998244353$ 取模。

输入格式

第一行输入一个整数 $n$ 。

第二行输入 $n$ 个整数 $A_1,A_2,...A_n$ 。

输出格式

答案输出 $10$ 行，第 $i$ 行表示剩下的数字为 $i-1$ 的情况数，答案对 $998244353$ 取模。

样例 #1

样例输入 #1

3
2 7 6

样例输出 #1

1
0
0
0
2
1
0
0
0
0

• 先加后乘： $(2,7,6) \rightarrow (9,6) \rightarrow (4)$ 。
• 两次加： $(2,7,6) \rightarrow (9,6) \rightarrow (5)$ 。
• 先乘后加： $(2,7,6) \rightarrow (4,6) \rightarrow (0)$ 。
• 两次乘： $(2,7,6) \rightarrow (4,6) \rightarrow (4)$ 。

样例 #2

样例输入 #2

5
0 1 2 3 4

样例输出 #2

6
0
1
1
4
0
1
1
0
2

提示

对于 $100\%$ 的数据：

• $2\ \leq\ N\ \leq\ 10^5$
• $0\ \leq\ A_i\ \leq\ 9$
• 所有的数据都是整数