102677: [AtCoder]ABC267 Ex - Odd Sum

Problem Statement

You are given a sequence $A=(A_1,A_2,\dots,A_N)$ of length $N$.

Find the number, modulo $998244353$, of ways to choose an odd number of elements from $A$ so that the sum of the chosen elements equals $M$.

Two choices are said to be different if there exists an integer $i (1 \le i \le N)$ such that one chooses $A_i$ but the other does not.

Constraints

• $1 \le N \le 10^5$
• $1 \le M \le 10^6$
• $1 \le A_i \le 10$
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

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

Output

Print the answer.

Sample Input 1

5 6
1 2 3 3 6

Sample Output 1

3

The following $3$ choices satisfy the condition:

• Choosing $A_1$, $A_2$, and $A_3$.
• Choosing $A_1$, $A_2$, and $A_4$.
• Choosing $A_5$.

Choosing $A_3$ and $A_4$ does not satisfy the condition because, although the sum is $6$, the number of chosen elements is not odd.

Sample Input 2

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

Sample Output 2

18

问题描述

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

求出以奇数个元素从$A$中选出，使得所选元素之和等于$M$的方法数（对$998244353$取模）。

如果存在一个整数$i (1 \le i \le N)$，使得一种选择选择了$A_i$，而另一种选择没有选择$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$

输出

输出答案。

样例输入 1

5 6
1 2 3 3 6

样例输出 1

3

有以下$3$种选择满足条件：

• 选择$A_1$，$A_2$和$A_3$。
• 选择$A_1$，$A_2$和$A_4$。
• 选择$A_5$。

选择$A_3$和$A_4$不满足条件，因为虽然和为$6$，但所选元素的数量不是奇数。

样例输入 2

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

样例输出 2

18