[ABC159F] Knapsack for All Segments

给定一个长度为 $N$ 的正整数序列 $A$。 定义 $f(L, R)$ 表示 $A$ 从 $L$ 位置到 $R$ 位置这一子串，有多少子序列的和等于 $S$。 求所有 $f(L, R)$ 的和。

[problemUrl]: https://atcoder.jp/contests/abc159/tasks/abc159_f 長さ $ 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 $ で割ったあまりを出力せよ。

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 $ つ)