← 返回题目列表

AtCoder · abc267_h

Ex. 奇数和

中文机器翻译题面 查看原题

分数: 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