配点 : $600$ 点

問題文

長さ $N$ の整数列 $A=(A_1,A_2,\dots,A_N)$ が与えられます。

$A$ から要素を奇数個選ぶ方法のうち、選んだ要素の総和が $M$ になるものの個数を $998244353$ で割ったあまりを求めてください。

ただし、$2$ つの選び方が異なるとは、ある整数 $i (1 \le i \le N)$ が存在して、一方の選び方では $A_i$ を選び、もう一方では選んでいないことを言います。

制約

• $1 \le N \le 10^5$
• $1 \le M \le 10^6$
• $1 \le A_i \le 10$
• 入力は全て整数。

入力

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

$N$ $M$

$A_1$ $A_2$ $\dots$ $A_N$

出力

答えを出力せよ。

5 6
1 2 3 3 6

3

条件を満たす選び方は以下の $3$ 通りです。

• $A_1,A_2,A_3$ を選ぶ。
• $A_1,A_2,A_4$ を選ぶ。
• $A_5$ を選ぶ。

$A_3,A_4$ を選んだ場合、総和は $6$ ですが選んだ要素の個数が奇数個でないため条件を満たしません。

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

18