分数: 600 点
问题陈述
求模数 998244353,序列 X 满足以下所有条件。
- 每学期 X 是一个积极的 奇数.
- 中各项的总和 X is S.
- 的前缀和 X 不包含任何 A_1, \dots, A_N。形式上,如果我们定义 Y_i = X_1 + \dots + X_i 对于每个 i,那么 Y_i \neq A_j 适用于所有整数 i 和 j 这样 1 \leq i \leq |X| 和 1 \leq j \leq N.
约束
- 1 \leq N \leq 10^5
- 1 \leq A_1 \lt A_2 \lt \dots \lt A_N \lt S \leq 10^{18}
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N S A_1 \ldots A_N
输出
打印答案。
示例输入 1
3 7 2 4 5
示例输出 1
3
以下三个序列满足条件。
- (1, 5, 1)
- (3, 3, 1)
- (7)
示例输入 2
5 60 10 20 30 40 50
示例输出 2
37634180
示例输入 3
10 1000000000000000000 1 2 4 8 16 32 64 128 256 512
示例输出 3
75326268