Ex - Odd Steps Editorial /

Time Limit: 3 sec / Memory Limit: 1024 MB

配点 : 600 点

問題文

以下の条件を全て満たす数列 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 が成り立つ。

制約

  • 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

以下の 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

Score : 600 points

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