3801: 学习 LIS(第五轮03)
题目描述
白浅妹妹前一段时间学习了 LIS（最长上升子序列）算法。
她随便生成了一个数组，这个数组长度是n，每个元素是一个[1, m]之间的正整数。
然后她开开心心的求出了这个数组的`LIS`数组，其中，第i个元素代表以原数组第i个数结尾 的最长上升子序列的长度是多少。
然而她把原数组弄丢了，请你帮她算算，原数组有多少种不同的可能。
输入
第一行两个正整数 n, m。
接下来一行， 一共 n 个正整数 a1, a2, . . . , an，表示原数组的 LIS 数组。
输出
输出符合条件的数组个数mod 998244353。
样例输入 复制
3 2
1 1 1样例输出 复制
4提示
【样例 1 输入】
3 2
1 1 1
【样例 1 输出】
4
【说明】
符合条件的数组有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
【备注】
对于测试点 1： 有：n, m ≤ 8。
对于测试点 2： 有：n, m ≤ 10。
对于测试点 3： 有：n ≤ 10,1 ≤ m ≤ 3000。
对于测试点 4：n ≤ 15, m ≤ 20。
对于测试点 5 ：n ≤ 15。
对于测试点 6：n ≤ 16, m ≤ 20。
对于测试点 7：n ≤ 16。
对于1 − 10测试点： 1 ≤ n ≤ 20,1 ≤ m ≤ 3000。