题目描述

小明前一段时间学习了LIS（最长上升子序列）算法，高兴的很啊。

他随便生成了一个数组，这个数组长度是$n$，每个元素是一个$[1,m]$之间的正整数。

然后他开开心心的求出了这个数组的LIS数组，其中，第$i$个元素代表以原数组第$i$个数结尾的最长上升子序列的长度是多少。

然而他把原数组弄丢了，请你帮他算算，原数组有多少种不同的可能。

输入格式

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

接下来一行，一共$n$个正整数$a_1,a_2,...,a_n$，表示原数组的LIS数组。

输出格式

输出符合条件的数组个数$mod\ 998244353$。

样例输入1

3 2
1 1 1

样例输出1

4

样例解释1

符合条件的数组有$4$个，分别是[1,1,1],[2,2,2],[2,1,1],[2,2,1]。

样例输入2

7 7
1 2 1 3 4 5 5

样例输出2

36

样例输入3

16 20
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

样例输出3

66951538

数据范围

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

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

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

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

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

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

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

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