题目描述

長さ $N$ の整数列 $A_1$, $A_2$, $\ldots$, $A_N$ と正の整数 $S$ が与えられます。
$1\leq\ L\ \leq\ R\ \leq\ N$ をみたす整数 $(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$ $...$ $A_N$

输出格式

$f(L,\ R)$ の和を $998244353$ で割ったあまりを出力せよ。

题目大意

给定一个长度为 $N$ 的正整数序列 $A$。

定义 $f(L, R)$ 表示 $A$ 从 $L$ 位置到 $R$ 位置这一子串，有多少子序列的和等于 $S$。

求所有 $f(L, R)$ 的和。

3 4
2 2 4

5

5 8
9 9 9 9 9

0

10 10
3 1 4 1 5 9 2 6 5 3

152

提示

制約

• 入力は全て整数である。
• $1\ \leq\ N\ \leq\ 3000$
• $1\ \leq\ S\ \leq\ 3000$
• $1\ \leq\ A_i\ \leq\ 3000$

Sample Explanation 1

それぞれ以下のように計算できて、その和は $5$ です。 - $f(1,1)\ =\ 0$ - $f(1,2)\ =\ 1$ ($(1,\ 2)$ の $1$ つ) - $f(1,3)\ =\ 2$ ($(1,\ 2)$ と $(3)$ の $2$ つ) - $f(2,2)\ =\ 0$ - $f(2,3)\ =\ 1$ ($(3)$ の $1$ つ) - $f(3,3)\ =\ 1$ ($(3)$ の $1$ つ)