题目描述

以下の条件を全て満たす数列 $X$ の総数を $998244353$ で割った余りを求めてください。

• $X$ の全ての項は正の奇数である。
• $X$ の各項の総和は $S$ に等しい。
• $X$ の累積和には $A_1,\ \dots,\ A_N$ のいずれも現れない。厳密には、各 $i\ \,\ (1\ \leq\ i\ \leq\ |X|)$ に対して $Y_i\ =\ X_1\ +\ \dots\ +\ X_i$ と定めたとき、$1\ \leq\ i\ \leq\ |X|,\ 1\ \leq\ j\ \leq\ N$ を満たす全ての整数 $i,\ j$ に対して $Y_i\ \neq\ A_j$ が成り立つ。

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $S$ $A_1$ $\ldots$ $A_N$

输出格式

答えを出力せよ。

题目大意

给定 $n, S$ 和序列 $A_n$，求任意长度的满足以下条件的序列个数：

• 仅由正奇数组成。
• 所有数之和为 $S$。
• 序列的任意前缀和均不能为 $A_n$ 中任意数。

答案对 $998244353$ 取模。

3 7
2 4 5

3

5 60
10 20 30 40 50

37634180

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

75326268

提示

制約

• $1\ \leq\ N\ \leq\ 10^5$
• $ 1\ \leq\ A_1\ \lt\ A_2\ \lt\ \dots\ \lt\ A_N\ \lt\ S\ \leq\ 10^{18} $
• 入力は全て整数

Sample Explanation 1

以下の $3$ 通りが条件を満たします。 - $(1,\ 5,\ 1)$ - $(3,\ 3,\ 1)$ - $(7)$