破门而入
题目描述
Kiana到一个密室中去探险寻宝,该密室中共有个房间,每个房间里都有一件独特的宝藏,而她此行的目的就是将所有房间中的宝藏全部取走。
可惜的是,密室的每个房间门都上了锁,而门锁的钥匙也放在这些房间中,具体来说,第号房间内放着第号房间的门钥匙,每扇门的钥匙有且只有一把,换句话说每个房间内放着的钥匙也是两两不同的。为了进入房间寻宝,Kiana可以选择直接暴力破开房门,也可以在拿到钥匙之后用钥匙文明地打开房门,但为了防止密室坍塌,Kiana至多只能使用暴力破开扇门。
聪明的Kiana计算出,房间中放钥匙的可能情况一共有种,而她想知道其中有多少种情况,使得自己合理选择暴力破开的门后能够最终成功取走所有房间的宝藏。由于Kiana自己不会算,所以希望你能够帮助她,但最后的答案可能很大,你只需告诉她答案对取模后的结果即可。
输入输出格式
输入格式
第一行包含两个正整数和,分别表示密室中的房间数和Kiana使用暴力能破坏的门数。
输出格式
输出共一行,包含一个非负整数,表示符合条件的情况数对取模后的结果。
输入输出样例
输入样例#1:
输出样例#1:
输入样例#2:
输出样例#2:
样例解释
在输入输出样例1中,密室内共有个房间,而Kiana只能使用暴力打开扇门,所有可能的情况如下:
号房间放着号门钥匙、号房间放着号门钥匙、号房间放着号门钥匙,此时Kiana没有办法取走所有宝藏
号房间放着号门钥匙、号房间放着号门钥匙、号房间放着号门钥匙,此时Kiana没有办法取走所有宝藏
号房间放着号门钥匙、号房间放着号门钥匙、号房间放着号门钥匙,此时Kiana没有办法取走所有宝藏
号房间放着号门钥匙、号房间放着号门钥匙、号房间放着号门钥匙,此时Kiana可以暴力破开号门,从号房间拿到号钥匙后打开号门,再从号房间拿到号钥匙后打开号门,取走所有宝藏
号房间放着号门钥匙、号房间放着号门钥匙、号房间放着号门钥匙,此时Kiana可以暴力破开号门,从号房间拿到号钥匙后打开号门,再从号房间拿到号钥匙后打开号门,取走所有宝藏
号房间放着号门钥匙、号房间放着号门钥匙、号房间放着号门钥匙,此时Kiana没有办法取走所有宝藏
综上所述,共有种符合条件的情况
数据范围
对于的数据,保证。
对于的数据,保证。
上面每一档数据中,各有一组数据保证,还有一组数据保证。
信息
- ID
- 1019
- 难度
- 9
- 分类
- (无)
- 标签
- (无)
- 递交数
- 1
- 已通过
- 1
- 通过率
- 100%
- 上传者