#6731. 「2019 山东一轮集训 Day3」小孩召开法

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

小孩召开法,

旦写一北砬。

梦厷停留在,

破了大式様。

——龚诗锋《炄勺,砒》

小弟递给神树大人一本《阿 Q 外教你学计数》,神树大人看了看第一题,发现不会;神树大人看了看第二题,发现题都读不懂;......;神树大人看了看第 114514 题,终于用 1919810 秒把它做了出来。他决定把这个题写进《神树大人教你做数学》。

对于长为 n 的一个排列 \{a_i\} 的一个子序列 a_{i_1},a_{i_2},\dots a_{i_k} ,如果这个子序列满足 a_{i_1}>a_{i_2}<a_{i_3}\dots >a_{i_k} ,那么这个子序列被称作交替子序列。你要求的就是最长的交替子序列等于 K 的长为 n 的排列有多少个,对 998244353 取模。

输入格式

输入 n,K

输出格式

输出一行答案。

样例

输入样例1

3 2

输出样例1

3

样例解释

序列 [1, 3, 2], [2, 3, 1], [3, 2, 1] 符合要求。

输入样例2

10 6

输出样例2

878856

输入样例3

5000 1145

输出样例3

849619090

数据范围与提示

提示:龚诗锋,小万邦,小弟是一个人。

另注:千万不要在这道题上浪费太多时间。

子任务 分数 n K
1 10 \leq 10 \leq n
2 20 \leq 5000
3 5 \leq 10^5 =n
4 10 \leq n
5 15 \leq 10^9 \leq \min(20,n)
6 5 \leq \min(200,n)
7 35 \leq 10^{18} \leq \min(10^6,n)