题目描述

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

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

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

输入格式

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

$N$ $M$ $A_1$ $A_2$ $\dots$ $A_N$

输出格式

答えを出力せよ。

题目大意

• 有一个长度为 $n$ 的数列 $A$，求出选出奇数个元素和为 $m$ 的方案数

• $n\le 10^5,m\le 10^6,a_i\le 10$

5 6
1 2 3 3 6

3

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

18

提示

制約

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

Sample Explanation 1

条件を満たす選び方は以下の $3$ 通りです。 - $A_1,A_2,A_3$ を選ぶ。 - $A_1,A_2,A_4$ を選ぶ。 - $A_5$ を選ぶ。 $A_3,A_4$ を選んだ場合、総和は $6$ ですが選んだ要素の個数が奇数個でないため条件を満たしません。