配点 : $600$ 点

問題文

クレーンゲームの大会で優勝した高橋君は金塊詰め放題の権利を得ました。 会場には $w_1 \lbrack\mathrm{kg}\rbrack, w_2 \lbrack\mathrm{kg}\rbrack, \dots, w_K \lbrack\mathrm{kg}\rbrack$ の重さの金塊、および金塊を詰める $1 \lbrack\mathrm{kg}\rbrack$ の袋が無尽蔵にあります。

高橋君は $1$ 個の空でない袋を持ち帰ることができます。 袋には $0$ 個以上の空でない袋と $0$ 個以上の金塊を入れることができます。

耐荷重量 $W \lbrack\mathrm{kg}\rbrack$ のトラックを手配した高橋君は、 $w = 2, 3, \dots, W$ について持ち帰る袋の総重量が $w \lbrack\mathrm{kg}\rbrack$ である詰め方としてあり得る状態の数が気になりました。 $w = 2, 3, \dots, W$ について状態数を $998244353$ で割ったあまりを求めてください。ただし、

• $2$ つの金塊が同じであるとは、金塊の重さが同じであることをいいます。
• $2$ つの袋が同じ状態であるとは、袋に入っている袋および金塊からなる多重集合が一致することをいいます。

制約

• $2 \leq W \leq 2.5 \times 10^5$
• $1 \leq K \leq W$
• $1 \leq w_i \leq W$ $(1 \leq i \leq K)$
• $i \neq j \to w_i \neq w_j$ $(1 \leq i,j \leq K)$
• 入力はすべて整数である。

入力

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

$W$ $K$

$w_1$ $w_2$ $\dots$ $w_K$

出力

答えを $W - 1$ 行出力せよ。 $i$ 行目には $w = i + 1$ のときの答えを出力せよ。

4 1
1

1
2
4

$w = 2, 3, 4$ において袋の状態としてあり得るものを列挙したのが下の図になります。 (丸い線が袋を表しています。)

10 10
1 2 3 4 5 6 7 8 9 10

1
3
7
18
45
121
325
904
2546