Score : $600$ points

问题陈述

求满足以下所有条件的序列 $X$ 的个数，结果对 $998244353$ 取模。

• 序列 $X$ 中的每个项都是一个正的奇数。
• $X$ 中各项之和为 $S$。
• $X$ 的前缀和中不包含任何 $A_1, \dots, A_N$。形式上，如果我们定义对于每个 $i$，$Y_i = X_1 + \dots + X_i$，则对于所有整数 $i$ 和 $j$（满足 $1 \leq i \leq |X|$ 且 $1 \leq j \leq N$），都有 $Y_i \neq A_j$。

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

Find the number, modulo $998244353$, of sequences $X$ that satisfy all of the following conditions.

• Every term in $X$ is a positive odd number.
• The sum of the terms in $X$ is $S$.
• The prefix sums of $X$ contain none of $A_1, \dots, A_N$. Formally, if we define $Y_i = X_1 + \dots + X_i$ for each $i$, then $Y_i \neq A_j$ holds for all integers $i$ and $j$ such that $1 \leq i \leq |X|$ and $1 \leq j \leq N$.

Constraints

• $1 \leq N \leq 10^5$
• $1 \leq A_1 \lt A_2 \lt \dots \lt A_N \lt S \leq 10^{18}$
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

$N$ $S$

$A_1$ $\ldots$ $A_N$

Output

Print the answer.

Sample Input 1

3 7
2 4 5

Sample Output 1

3

The following three sequences satisfy the conditions.

• $(1, 5, 1)$
• $(3, 3, 1)$
• $(7)$

Sample Input 2

5 60
10 20 30 40 50

Sample Output 2

37634180

Sample Input 3

10 1000000000000000000
1 2 4 8 16 32 64 128 256 512

Sample Output 3

75326268

update @ 2024/3/10 10:58:41