考虑正难则反，答案即为(n!- ext{返回值为n的排列数})
一个排列的返回值为(n)，当且仅当在(n)出现之前没有一个数后面有连续(k)个小于它的数
设(f_i)表示(1)到(i)的排列中，没有任何一个数后面有连续(k)个小于它的数
枚举(i)的位置，则有
[f_i=sum_{j=1}^kA_{i-1}^{j-1}f_{i-j}
]
即把(i)放在倒数第(j)个位置，从(1)到(i-1)中选(j-1)个数排列在(i)后面，剩下(i-j)个个数放在(i)前面并且保证合法
把排列数打开，就变成了(f_i=(i-1)!sum_{j=1}^{k}frac{f_{i-j}}{(i-j)!})
维护一下(frac{f_i}{i!})的前缀和就可以快速转移了
枚举一下(n)所在的位置，返回值为(n)的排列数即为
[sum_{i=1}^nf_{i-1}inom{n-1}{i-1}(n-i)!
]
代码
#include<bits/stdc++.h>
#define re register
#define LL long long
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
inline int read() {
char c=getchar();int x=0;while(c<'0'||c>'9') c=getchar();
while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-48,c=getchar();return x;
}
const int mod=1e9+7;
const int maxn=1e6+5;
int pre[maxn],fac[maxn],ifac[maxn],inv[maxn],f[maxn];
int n,m;
inline int C(int n,int m) {
if(n<m) return 0;
return 1ll*fac[n]*ifac[n-m]%mod*ifac[m]%mod;
}
inline int qm(int x) {return x>=mod?x-mod:x;}
inline int dqm(int x) {return x<0?x+mod:x;}
inline int calc(int l,int r) {
if(l<=0) return pre[r];
return dqm(pre[r]-pre[l-1]);
}
int main() {
n=read(),m=read();fac[0]=ifac[0]=inv[1]=1;
for(re int i=1;i<=n;i++) fac[i]=1ll*fac[i-1]*i%mod;
for(re int i=2;i<=n;i++) inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
for(re int i=1;i<=n;i++) ifac[i]=1ll*ifac[i-1]*inv[i]%mod;
f[0]=1;pre[0]=1;
for(re int i=1;i<n;i++) {
f[i]=1ll*calc(i-m,i-1)*fac[i-1]%mod;
pre[i]=qm(pre[i-1]+1ll*f[i]*ifac[i]%mod);
}
int ans=0;
for(re int i=1;i<=n;i++)
ans=qm(ans+1ll*f[i-1]*C(n-1,i-1)%mod*fac[n-i]%mod);
printf("%d
",dqm(fac[n]-ans));
return 0;
}