分数: 600 点
问题陈述
给你一个序列 A=(A_1,A_2,\dots,A_N) 长度 N.
求模数 998244353,从中选择奇数个元素的方法 A 使得所选元素的总和等于 M.
如果存在一个整数,则两个选择不同 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
输出
打印答案。
示例输入 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