F-所有子序列背包问题

给定一个长度为N的整数序列 $A_1$, $A_2$, $\ldots$, $A_N$ 和一个正整数S。

对于一个整数对$(L, R)$，满足$1\leq L \leq R \leq N$，定义$f(L, R)$如下：

$f(L, R)$是满足条件 $L \leq x_1 < x_2 < \cdots < x_k < 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$取模后输出。

限制条件

• 输入中的所有值都是整数。
• $1 \leq N \leq 3000$
• $1 \leq S \leq 3000$
• $1 \leq A_i \leq 3000$

输入

输入以以下格式从标准输入给出。

$N$ $S$

$A_1$ $A_2$ $...$ $A_N$

输出

输出$f(L, R)$的总和，对$998244353$取模

输入样例1

3 4
2 2 4

输出样例1

5

$f(L, R)$的值如下，总和为$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)$）

输入样例2

5 8
9 9 9 9 9

输出样例2

0

输入样例3

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

输出样例3

152