AT_abc159_f.[ABC159F] Knapsack for All Segments

给定一个长度为 $N$ 的整数序列 $A_1, A_2, \ldots, A_N$ 和一个正整数 $S$。
对于所有满足 $1 \leq L \leq R \leq N$ 的整数对 $(L, R)$，定义 $f(L, R)$ 如下：

• $f(L, R)$ 表示满足 $L \leq x_1 < x_2 < \cdots < x_k \leq R$ 且 $A_{x_1} + A_{x_2} + \cdots + A_{x_k} = S$ 的整数序列 $(x_1, x_2, \ldots, x_k)$ 的个数。

请计算所有满足 $1 \leq L \leq R \leq N$ 的整数对 $(L, R)$ 的 $f(L, R)$ 之和。由于答案可能非常大，请输出其对 $998244353$ 取模的结果。

输入以如下格式从标准输入读入。

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

输出所有 $f(L, R)$ 之和对 $998244353$ 取模的结果。

限制条件

• 输入均为整数。
• $1 \leq N \leq 3000$
• $1 \leq S \leq 3000$
• $1 \leq A_i \leq 3000$

样例解释 1

可以分别计算如下，和为 $5$。

• $f(1,1) = 0$
• $f(1,2) = 1$（仅有 $(1, 2)$ 这一种情况）
• $f(1,3) = 2$（$(1, 2)$ 和 $(3)$ 两种情况）
• $f(2,2) = 0$
• $f(2,3) = 1$（仅有 $(3)$ 这一种情况）
• $f(3,3) = 1$（仅有 $(3)$ 这一种情况）

由 ChatGPT 4.1 翻译