配点 : $400$ 点

問題文

$0$ 以上 $9$ 以下の整数からなる長さ $N$ の数列 $A=(A_1,\dots,A_N)$ があり、この順に左から右に並んでいます。

数列の長さが $1$ になるまで、操作 $F$ または操作 $G$ を繰り返し行います。

• 操作 $F$ ：左端の $2$ つの値 ( $x,y$ とする ) を削除した後、一番左に $(x+y)\%10$ を挿入する
• 操作 $G$ ：左端の $2$ つの値 ( $x,y$ とする ) を削除した後、一番左に $(x\times y)\%10$ を挿入する

なお、$a\%b$ は $a$ を $b$ で割った余りを意味します。

$K=0,1,\dots,9$ について、以下の問題に答えてください。

操作手順としてあり得るものは $2^{N-1}$ 通りありますが、このうち最終的に残る値が $K$ となる操作手順は何通りありますか？ ただし答えは非常に大きくなる可能性があるので、$998244353$ で割った余りを求めてください。

制約

• $2 \leq N \leq 10^5$
• $0 \leq A_i \leq 9$
• 入力は全て整数

入力

入力は以下の形式で標準入力から与えられる。

$N$

$A_1$ $\dots$ $A_N$

出力

答えを $10$ 行に出力せよ。 ただし、$i$ 行目には $K=i-1$ としたときの答えを出力せよ。

3
2 7 6

1
0
0
0
2
1
0
0
0
0

$1$ 回目に操作 $F$ 、$2$ 回目に操作 $F$ を行ったとき：数列は $(2,7,6) \to (9,6) \to (5)$ となります。 $1$ 回目に操作 $F$ 、$2$ 回目に操作 $G$ を行ったとき：数列は $(2,7,6) \to (9,6) \to (4)$ となります。 $1$ 回目に操作 $G$ 、$2$ 回目に操作 $F$ を行ったとき：数列は $(2,7,6) \to (4,6) \to (0)$ となります。 $1$ 回目に操作 $G$ 、$2$ 回目に操作 $G$ を行ったとき：数列は $(2,7,6) \to (4,6) \to (4)$ となります。

5
0 1 2 3 4

6
0
1
1
4
0
1
1
0
2