首页 > 试题广场 >

队列重排

[编程题]队列重排

时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

有n(n≤500000) 个人排成一列，把他们解散后重排，使得"重排后前方" 跟"原排列前方" 一样的人不超过k(k<n) 个，问有几种方法数，答案请mod (10⁹+7) 输出。
举例来说，有五个人编号为1∼5 间的整数，最初的排列由前至后依序为1, 2, 3, 4, 5，重排列后顺序由前至后变为1, 3, 4, 2, 5，其中只要编号为4 的人，"原排列前方" 跟"重排后前方" 都是编号为3 的人，故"重排后前方" 跟"原排列前方" 一样的人只有1 人。
原排列的第 1 个人和重排后的第 1 个人一定不会是「"重排后前方" 跟 "原排列前方" 一样的人」。

输入描述:

输入只有一行，有两个正整数 n,k，满足 1≤k<n≤500000。

输出描述:

请输出一行包含一个小于 10⁹+7 的非负整数，表示总共的方法数 mod (10⁹+7)。

示例1

输入

3 1

输出

说明

当 n=3 时，假设三个人在原排列的编号由前到后依序为 1、2、3。
重排列后的情形可分为下列 3 种：
"重排后前方" 和 "原排列前方" 一样的人数为 0 的有：1 3 2,2 1 3,3 2 1,3 种。
"重排后前方" 和 "原排列前方" 一样的人数为 1 的有：2 3 1,3 1 2,2 种。
"重排后前方" 和 "原排列前方" 一样的人数为 2 的仅有 1 2 3,1 种。

示例2