题目描述

小 P 有一个长度为 $N$ 的正整数序列 $A_1, A_2, \ldots, A_N$ 和一个目标正整数 $S$。他对序列的每一个连续片段都提出同一个问题。

具体地，对于满足 $1 \le L \le R \le N$ 的片段 $A_L, A_{L+1}, \ldots, A_R$，定义 $f(L, R)$ 为：从该片段中选出若干个位置 $L \le x_1 < x_2 < \cdots < x_k \le R$，使得 $A_{x_1} + A_{x_2} + \cdots + A_{x_k} = S$ 的方案数。一个位置至多选一次，不同选位置的方式视为不同方案。由于 $S \ge 1$，"一个位置都不选"的和为 $0$，不会被计入。

小 P 想把所有片段的 $f(L, R)$ 加起来，即求

由于结果可能很大，你只需要输出该和对 $998244353$ 取模的结果。

输入格式

从标准输入读入数据。

第一行两个正整数 $N$ 和 $S$，用一个空格分隔。

第二行 $N$ 个正整数 $A_1, A_2, \ldots, A_N$，表示序列，相邻两数用一个空格分隔。

输出格式

输出到标准输出。

输出一个整数，表示所有片段的 $f(L, R)$ 之和对 $998244353$ 取模的结果。

样例

样例 1 输入

4 3
1 2 1 3

样例 1 输出

11

样例 1 解释

序列为 $[1, 2, 1, 3]$，$S = 3$。逐个片段计算 $f(L, R)$：

• $f(1,1)=0$，$f(1,2)=1$（选 $A_1, A_2$），$f(1,3)=2$（选 $A_1,A_2$ 或 $A_2,A_3$），$f(1,4)=3$（再增加单独选 $A_4$）；
• $f(2,2)=0$，$f(2,3)=1$（选 $A_2,A_3$），$f(2,4)=2$（再增加单独选 $A_4$）；
• $f(3,3)=0$，$f(3,4)=1$（选 $A_4$）；
• $f(4,4)=1$（选 $A_4$）。

总和为 $0+1+2+3+0+1+2+0+1+1=11$。

样例 2 输入

4 11
1 2 3 4

样例 2 输出

0

样例 2 解释

整个序列所有数之和为 $1+2+3+4=10$，已经小于 $S=11$，因此没有任何子序列的和能等于 $11$，所有 $f(L, R)$ 均为 $0$，答案为 $0$。

样例 3 输入

8 5
2 3 1 1 2 4 1 3

样例 3 输出

100

样例 3 解释

片段较多，按定义逐个累加 $f(L, R)$ 即可得到 $100$。

数据范围

对于所有数据：

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

本题采用捆绑测试。只有通过一个子任务的全部测试，才能获得该子任务的分数。

• 子任务 $1$（$10$ 分）：$N \le 20$。
• 子任务 $2$（$15$ 分）：$N \le 100$。
• 子任务 $3$（$20$ 分）：$S = 1$。
• 子任务 $4$（$20$ 分）：$A_i = 1$，其中 $1 \le i \le N$。
• 子任务 $5$（$35$ 分）：无附加限制。

提示

• 答案对 $998244353$ 取模后输出；该数为质数。
• 同一个片段内，每个位置至多被选一次，不同选位置的方式计为不同方案。