奇数个元素的和

题目描述

给定长度为 $N$ 的序列 $A=(A_1,A_2,\dots,A_N)$。

求从 $A$ 中选择奇数个元素，使所选元素的和恰好等于 $M$ 的方案数，结果对 $998244353$ 取模。

若存在一个整数 $i (1 \le i \le N)$，使得一种选择包含 $A_i$ 而另一种选择不包含，则称这两种选择不同。

输入格式

输入按以下格式从标准输入给出：

$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

数据范围

• $1 \le N \le 10^5$
• $1 \le M \le 10^6$
• $1 \le A_i \le 10$
• 输入中的所有值均为整数