#p Subset Sum 5

2 secs 1024 MB
RINE's icon RINE

問題文

NN 個の正整数 s1,s2,,sNs_1, s_2, \cdots, s_N と正整数 TT が与えられます。

t=1,2,,Tt = 1, 2, \cdots, T について部分集合 I{1,2,,N}I \subseteq \{1, 2,\cdots, N\} のうち、 I1(mod2)|I| \equiv 1 \pmod 2 かつ iIsi=t\sum_{i \in I} s_i = tとなるものの個数を 998244353998244353 で割った余り ptp_t を求めてください。

制約

  • 1N,T100,0001 \le N, T \le 100,000
  • 1siT1 \le s_i \le T
  • 入力はすべて整数

入力

入力
N T
s1 ... sN

出力

p1 p2 ... pT

サンプル

1

5 3
1 1 2 2 3
2 2 1

提出


Go (1.21)