QOJ.ac

QOJ

Time Limit: 2 s Memory Limit: 512 MB Total points: 100
统计

给定 $ n,k $,设 $ p $ 是一个 $ n $ 阶排列,你可以将 $ p $ 划分成恰好 $ k $ 个非空连续段(也即,选择 $ k-1 $ 个断点 $ 1\le x_1 < x_2 < \cdots < x_{k-1} < n $,令划分为 $ [1, x_1], (x_1, x_2], \cdots, (x_{k-1}, n] $),然后将每段内部的数从小到大排序,得到一个新的排列 $ q $。

定义 $ f(p) $ 表示,所有划分方案里可能得到的 $ q $ 中字典序最小的那一个。

现在给定一个 $ n $ 阶排列 $ q $,求有多少个 $ n $ 阶排列 $ p $ 的 $ f(p)=q $。请输出答案模 $ 998244353 $ 的值。

输入格式

第一行两个数 $ n,k $。

第二行 $ n $ 个数,表示排列 $ q $。

输出格式

一行一个数,表示答案。

样例

样例 1
2 1
1 2
2
样例 2
3 3
3 1 2
1
样例 3
6 3
1 2 3 6 5 4
13

数据范围

对于所有数据,$ 1\le n\le 500,1\le k \le n $。

子任务 1(10%):$ n\le 6 $。

子任务 2(20%):$ n\le 10 $。

子任务 3(30%):$ q=(1,2,\cdots,n) $。

子任务 4(40%):无特殊限制。