問題文

$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$ としたときの答えを出力せよ。

入力例 1

3
2 7 6

出力例 1

1
0
0
0
2
1
0
0
0
0

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

入力例 2

5
0 1 2 3 4

出力例 2

6
0
1
1
4
0
1
1
0
2