题目背景

小 L 很喜欢吃零食。

题目描述

提交时自动开启 O2 优化。

小 L 现在想把一些零食放在一个盒子里。但是零食没放稳就会摔坏，所以小 L 希望求出有多少种稳定的堆放零食的方法。

零食都可以抽象成一个 $1\times1$ 的正方形，而盒子的底部可以看成长度为 $n$ 的一维线段。准确地说，零食被分为 $n$ 堆，从左到右地放在盒子里面，依次记为第 $1,2,\ldots,n$ 堆。我们认为每一堆的高度 $h_i$ 是这一堆零食的数量，且任意一堆都可以不包含任何零食。

我们定义第 $i$ 堆零食是稳定的，当且仅当：

• $h_i\le m$，即这一堆零食高度不超过 $m$。
• 在满足上一条的同时，满足以下两条之一或同时满足：
  • $i=1$ 或 $i=n$，此时有一侧是盒子内壁所以这一堆不会倒下；
  • $\color{red}\max\{h_{i-1},h_{i+1}\}\ge h_i-d_i$，此时它两侧的两堆零食有一堆足够高可以支撑这一堆不倒下。

我们定义一种稳定的堆放零食的方法，是一个长度为 $n$ 的 $h_i$ 的序列，满足按这个序列堆放出来的零食每一堆都是稳定的。

显然盒子里最多放下 $n\times m$ 个零食，我们认为小 L 的零食数量不少于 $n\times m$，并且不必将所有零食全部放进盒子。额外地，我们认为每一个零食都是完全一样的。

输入格式

总共包括 $2$ 行。

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

第二行包含 $n$ 个整数 $d_1,d_2\ldots,d_n$，意义如【题目描述】中红色部分所示。

每行的两个数字间由单个空格隔开，数据在 Windows 下生成。行末不保证没有多余空格。

输出格式

一行一个整数，表示有多少种稳定的堆放零食的方法，结果对 $998244353$ 取模。

3 3
3 1 1 

59

10 13
12 13 1 4 5 9 7 0 3 8 

851695394

提示

本题采用如下计分策略：
subtask $1$（#$1$~#$8$）：$10\%$，$n,m\le5$；
subtask $2$（#$9$~#$12$）：$30\%$，$n,m\le5\times10^2$；
subtask $3$（#$13$~#$16$）：$20\%$，$n,m\le3\times10^3$；
subtask $4$（#$17$~#$24$）：$40\%$，$n,m\le7\times10^3$。
对于 $100\%$ 的数据：$1\le n,m\le7\times10^3$，$0\le d_i\le m$。你必须通过一个 subtask 内所有测试点，才被认为通过该 subtask。

本题开启子任务依赖。