分数: 600 点
问题陈述
给出了一系列 N 整数 A_1, A_2, \ldots, A_N 和一个正整数 S.
对于一对整数 (L, R) 这样 1\leq L \leq R \leq N,让我们定义 f(L, R) 如下:
- f(L, R) 是整数序列的数量 (x_1, x_2, \ldots , x_k) 这样 L \leq x_1 < x_2 < \cdots < x_k \leq R 和 A_{x_1}+A_{x_2}+\cdots +A_{x_k} = S.
求总和 f(L, R) 所有整数对 (L, R) 这样 1\leq L \leq R\leq N。由于这个和可能是巨大的,所以打印它的模 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