最后的数

题目描述

Orange有一个整数序列 $a_i$，它们被存放进一个栈(Stack)中，序列的左端为栈顶，右端为栈底。同时，这些数都只包含一个数位，即 $0 \le a_i \le 9$。

Orange每次可以从栈中取出两个位于栈顶的数，记为 $u$ 和 $v$，现在Orange可以执行以下两种操作中的一种：

• 操作 $1$ : 将它们的乘积的最低位入栈，并舍弃 $u$ 和 $v$。形式化的说，将 $(u \times v) \bmod10$ 入栈。
• 操作 $2$ : 将它们的和的最低位入栈，并舍弃 $u$ 和 $v$。形式化的说，将 $(u + v) \bmod10$ 入栈。

显然，每次操作都会让栈中减少一个元素，我们将在栈中只剩下最后一个元素时终止操作。我们将每次操作的顺序记成一个序列，现在Orange想知道，有多少种操作序列可以让最后剩下的数为 $i$。

由于最后的答案会非常大，你只需要输出每个 $i$ 对应的答案 $\bmod \ 998244353$ 即可。

输入格式

输入包含 2 行： 第一行仅包含一个整数 $n$，表示序列长度。 第二行包含 $n$ 个整数 $a_i$，表示序列的每个元素 $a_i$。

数据范围

对于 $20\%$ 的数据，$1\le n \le 20$。 对于所有数据: $1\le n \le 2 \times 10^5$ $0 \le a_i \le 10$

输出格式

输出包含10行，其中第 $i$ 行包含一个整数，表示最后的数为 $i - 1$ 的操作序列种类数量。

样例 #1

样例输入 #1

4
2 3 7 6

样例输出 #1

1
1
2
0
0
0
0
0
3
1