AT_npcapc_2024_b Some Sum of Subset

長さ $ 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 $ を満たすものが存在する。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ A_1 $ $ A_2 $ $ \dots $ $ A_N $

$ N+1 $ 行に渡って出力せよ。 $ i(1\le i\le N+1) $ 行目には、 $ k=i-1 $ の場合の答えを出力すること。

### Sample Explanation 1 $ 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 $ です。 ### Constraints - $ 1 \le N \le 3000 $ - $ 1 \le M \le 3000 $ - $ 1 \le A_i \le 3000 $