You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

标题来自 心を刺す言葉だけ (feat. 初音ミク & 可不)。

题目描述

有 $n$ 种颜料和一个长度为 $m$ 的画板，颜色分别为 $1,2,\cdots,n$。第 $i$ 个颜料有 $c_i$ 桶。

现在你可以用一个笔刷在这个画板上画 $n$ 段，具体来说，你可以选择任意一个 $1\le p\le m$ 作为你一开始的位置，接下来依次对每个 $i=1,2,\cdots,n$，你可以将笔刷从当前位置 $p$ 向左或向右移动 $c_i$ 格，即移动到 $q=p-c_i+1$ 或 $q=p+c_i-1$ 处，并将 $p,q$ 之间的位置（包括 $p,q$）都染成第 $i$ 种颜色。

这里要求新的位置 $q$ 不能超出画板的边界，即 $1\le q\le m$。

如果一个位置被染色多次，我们认为这个位置的颜色是它最后一次染上的颜色；如果一个位置没有被染色，我们认为这个位置的颜色为 $0$。现在你需要求出染色完成后可以得到多少种不同的画板，答案对 $998244353$ 取模。

这里两个最终画板是不同的，当且仅当存在至少一个位置 $i$ 满足这两个画板在第 $i$ 个位置上的颜色不同。

输入格式

第一行两个正整数 $n,m$。

第二行 $n$ 个正整数 $c_1,c_2,\cdots,c_n$。

输出格式

输出一行一个正整数表示答案。

样例 $1$ 输入

4 4
2 3 1 2

样例 $1$ 输出

8

样例 $1$ 解释

共有 $8$ 种可能的序列：

0 2 4 4
0 4 4 2
1 2 4 4
2 2 4 4
2 4 4 0
4 4 2 0
4 4 2 1
4 4 2 2

样例 $2$ 输入

5 6
2 3 2 2 3

样例 $2$ 输出

36

样例 $3$ 输入

6 8
2 4 3 5 2 1

样例 $3$ 输出

42

样例 $4$ 输入

12 21
8 2 6 9 9 9 10 8 2 6 5 9

样例 $4$ 输出

760

测试点约束

对于 $100\%$ 的数据，$2\le n,m\le 150,1\le c_i\le m$。