[ABC258Ex] Odd Steps
题意翻译
给定 $ n, S $ 和序列 $ A_n $，求任意长度的满足以下条件的序列个数：
* 仅由正奇数组成。
* 所有数之和为 $ S $。
* 序列的任意前缀和均不能为 $ A_n $ 中任意数。
答案对 $ 998244353 $ 取模。
题目描述
[problemUrl]: https://atcoder.jp/contests/abc258/tasks/abc258_h
以下の条件を全て満たす数列 $ 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 $
输出格式
答えを出力せよ。
输入输出样例
输入样例 #1
3 7
2 4 5输出样例 #1
3输入样例 #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说明
### 制約
- $ 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) $