問題文

長さ N の正整数列 A=(A_1,A_2,\dots,A_N) が与えられます。k=0,1,\dots,N について以下の問題を解いてください。

\lbrace 1,2,\dots,N\rbrace の部分集合 S であって以下の条件を満たすものの個数を 998244353 で割ったあまりを求めてください。

• \left\vert T\right\vert=\left\vert S\right\vert-k を満たす S の部分集合 T であって \sum_{i \in T}A_{i}\ge M を満たすものが存在する。

制約

• 1 \le N \le 3000
• 1 \le M \le 3000
• 1 \le A_i \le 3000

入力例 1

4 7
3 1 5 2

出力例 1

6
4
1
0
0

k=1 のときを例に挙げて説明します。

• S=\lbrace 1,3,4\rbrace は、T=\lbrace 3,4\rbrace とすると \left\vert T\right\vert=\left\vert S\right\vert-1 かつ \sum_{i\in T} A_i \ge 7 となるため条件を満たします。

他には、S=\lbrace 1,2,3\rbrace,\lbrace 2,3,4\rbrace,\lbrace 1,2,3,4\rbrace の 3 個が条件を満たします。よって、k = 1 のとき答えは 4 です。

入力例 2

1 5
7

出力例 2

1
0

入力例 3

9 18
1 9 5 6 2 7 1 4 8

出力例 3

346
309
230
126
46
10
1
0
0
0