题目描述

1s，512M，seq.in，seq.out。

给定长度为 $n$ 的序列 $h$ ，你需要求出有多少个不同的长度为 $n$ 的序列 $a$ 满足

• $a_1\ge 1$ ，$a_n\le k$ 。
• 对于任意的 $1\le i <n$ ， $h_i+a_i\le h_{i+1}+a_{i+1}$ 。

这样的序列可能很多，你只需要输出答案对 $998244353$ 取模后的结果。

输入格式

第一行两个整数 $n,k$ 表示序列长度，和 $a_n$ 的最大值。

第二行包含 $n$ 个整数，第 $i$ 个整数表示 $h_i$ 。

输出格式

一行一个整数表示答案对 $998244353$ 取模后的结果。

样例 #1

样例输入 #1

3 3
3 2 1

样例输出 #1

1

样例 #2

样例输入 #2

5 10
4 6 3 2 7

样例输出 #2

6188

提示

对于 $5\%$ 的数据 ， $n\le 2$ 。

对于 $15\%$ 的数据 ， $n\le 3$ 。

对于 $30\%$ 的数据 ， $n,k,h_i\le 100$

对于 $50\%$ 的数据 ， $n,k,h_i\le 1000$

对于 $100\%$ 的数据 ， $n\le 10^6$，$1\le k,h_i< 2^{31}$ 。