Score : $475$ points

问题陈述

给定一个长度为 $N$ 的序列 $A = (A_1, A_2, \dots, A_N)$ 和一个整数 $K$。 将 $A$ 分割成几个连续子序列有 $2^{N-1}$ 种方式。有多少种分割方式使得没有子序列的元素之和等于 $K$？求出这个数量对 $998244353$ 取模的结果。

这里，“将 $A$ 分割成几个连续子序列”意味着以下过程：

• 自由选择子序列的数量 $k$ $(1 \leq k \leq N)$ 和一个整数序列 $(i_1, i_2, \dots, i_k, i_{k+1})$，满足 $1 = i_1 < i_2 < \dots < i_k < i_{k+1} = N+1$。
• 对于每个 $1 \leq n \leq k$，第 $n$ 个子序列由取 $A$ 中第 $i_n$ 个到第 $(i_{n+1} - 1)$ 个元素组成，保持它们的顺序。

以下是 $A = (1, 2, 3, 4, 5)$ 的一些分割示例：

• $(1, 2, 3), (4), (5)$
• $(1, 2), (3, 4, 5)$
• $(1, 2, 3, 4, 5)$

以上为大语言模型 kimi 翻译，仅供参考。

Problem Statement

You are given a sequence $A = (A_1, A_2, \dots, A_N)$ of length $N$ and an integer $K$.
There are $2^{N-1}$ ways to divide $A$ into several contiguous subsequences. How many of these divisions have no subsequence whose elements sum to $K$? Find the count modulo $998244353$.

Here, "to divide $A$ into several contiguous subsequences" means the following procedure.

• Freely choose the number $k$ $(1 \leq k \leq N)$ of subsequences and an integer sequence $(i_1, i_2, \dots, i_k, i_{k+1})$ satisfying $1 = i_1 \lt i_2 \lt \dots \lt i_k \lt i_{k+1} = N+1$.
• For each $1 \leq n \leq k$, the $n$-th subsequence is formed by taking the $i_n$-th through $(i_{n+1} - 1)$-th elements of $A$, maintaining their order.

Here are some examples of divisions for $A = (1, 2, 3, 4, 5)$:

• $(1, 2, 3), (4), (5)$
• $(1, 2), (3, 4, 5)$
• $(1, 2, 3, 4, 5)$

Constraints

• $1 \leq N \leq 2 \times 10^5$
• $-10^{15} \leq K \leq 10^{15}$
• $-10^9 \leq A_i \leq 10^9$
• All input values are integers.

Input

The input is given from Standard Input in the following format:

$N$ $K$

$A_1$ $A_2$ $\dots$ $A_N$

Output

Print the count modulo $998244353$.

Sample Input 1

3 3
1 2 3

Sample Output 1

2

There are two divisions that satisfy the condition in the problem statement:

• $(1), (2, 3)$
• $(1, 2, 3)$

Sample Input 2

5 0
0 0 0 0 0

Sample Output 2

0

Sample Input 3

10 5
-5 -1 -7 6 -6 -2 -5 10 2 -10

Sample Output 3

428