题目描述

相信你看到题目名字的时候就感觉不是很难了。

现在给你一个正整数序列$a$，序列长度为$n$，对于每个元素$a_i$有$1 \le a_i \le m$。

给出该序列以第$i$个元素结束的最长上升子序列长度，记为$b_i$。

你的任务是计数有多少种不同的构造$a_i$的方案，使得它满足给出的$b_i$。

方案可能很多，对$998244353$取模。

输入格式

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

接下来一行$n$个整数，依次表示题目中描述的$b_i$。

输出格式

输出符合题目要求的数组数量mod 998244353。

3 2
1 1 1

4

样例解释

符合的序列有：

• [1, 1, 1]
• [2, 2, 2]
• [2, 1, 1]
• [2, 2, 1]

数据范围

对于10%的数据：$n, m \le 8$。

对于20%的数据：$n, m \le 10$。

对于30%的数据：$n \le 10$。

对于另10%的数据：$n \le 15, m \le 20$。

对于另10%的数据：$n \le 15$。

对于另10%的数据：$n \le 16, m \le 20$。

对于另10%的数据：$n \le 16$。

对于100%的数据：$1 \le n \le 20, 1 \le m \le 3000$。

下发样例