破门而入

题目描述

​ Kiana到一个密室中去探险寻宝,该密室中共有nn个房间,每个房间里都有一件独特的宝藏,而她此行的目的就是将所有房间中的宝藏全部取走。
​ 可惜的是,密室的每个房间门都上了锁,而门锁的钥匙也放在这些房间中,具体来说,第ii号房间内放着第aia_i号房间的门钥匙,每扇门的钥匙有且只有一把,换句话说每个房间内放着的钥匙也是两两不同的。为了进入房间寻宝,Kiana可以选择直接暴力破开房门,也可以在拿到钥匙之后用钥匙文明地打开房门,但为了防止密室坍塌,Kiana至多只能使用暴力破开kk扇门。
​ 聪明的Kiana计算出,房间中放钥匙的可能情况一共有n!n!种,而她想知道其中有多少种情况,使得自己合理选择暴力破开的门后能够最终成功取走所有房间的宝藏。由于Kiana自己不会算,所以希望你能够帮助她,但最后的答案可能很大,你只需告诉她答案对998244353998244353取模后的结果即可。

输入输出格式

输入格式
第一行包含两个正整数nnkk,分别表示密室中的房间数和Kiana使用暴力能破坏的门数。
输出格式
输出共一行,包含一个非负整数,表示符合条件的情况数对998244353998244353取模后的结果。

输入输出样例

输入样例#1:

3 1

输出样例#1:

输入样例#2:

broken2.in

输出样例#2:

broken2.out

样例解释

在输入输出样例1中,密室内共有33个房间,而Kiana只能使用暴力打开11扇门,所有可能的情况如下:
11号房间放着11号门钥匙、22号房间放着22号门钥匙、33号房间放着33号门钥匙,此时Kiana没有办法取走所有宝藏
11号房间放着11号门钥匙、22号房间放着33号门钥匙、33号房间放着22号门钥匙,此时Kiana没有办法取走所有宝藏
11号房间放着22号门钥匙、22号房间放着11号门钥匙、33号房间放着33号门钥匙,此时Kiana没有办法取走所有宝藏
11号房间放着22号门钥匙、22号房间放着33号门钥匙、33号房间放着11号门钥匙,此时Kiana可以暴力破开11号门,从11号房间拿到22号钥匙后打开22号门,再从22号房间拿到33号钥匙后打开33号门,取走所有宝藏
11号房间放着33号门钥匙、22号房间放着11号门钥匙、33号房间放着22号门钥匙,此时Kiana可以暴力破开11号门,从11号房间拿到33号钥匙后打开33号门,再从33号房间拿到22号钥匙后打开22号门,取走所有宝藏
11号房间放着33号门钥匙、22号房间放着22号门钥匙、33号房间放着11号门钥匙,此时Kiana没有办法取走所有宝藏
综上所述,共有22种符合条件的情况

数据范围

对于30%30\%的数据,保证1kn101\leq k\leq n\leq 10
对于100%100\%的数据,保证1kn30001\leq k\leq n\leq 3000
上面每一档数据中,各有一组数据保证k=1k=1,还有一组数据保证k=2k=2

信息

ID
1019
难度
9
分类
(无)
标签
(无)
递交数
1
已通过
1
通过率
100%
上传者