cf886E

Description

对于一个 个数的排列，定义这个排列的极大值为第一个满足它比后面的 个数都大的数（如果后面不足 个则只需要比后面的数大即可）

给定 求有多少个长为 的排列满足其极大值不为 ，对 取模。

Input

一行两个整数

Output

一行一个整数，即满足条件的排列个数

Sample Input

5 2

5 3

6 3

Sample Output

22

6

84

Hint

样例二的所有情况：

Solution

考虑容斥计算所有合法的情况

定义 为 个数极大值在最后 个中（如果 则任意）的排列数（可以发现这时最大值一定等于极大值））。

（这样定义是因为在后面接上一个更大的数则极大值就一定不在这前面 个数之中）

转移是枚举这 个数中的最大值 在最后 个数中的哪一个，右边任意排列且左边的极大值在左边的最后 个中（这样才能被新加入的 覆盖掉）的方案数

可以通过计算 的前缀和来加速转移

所有极大值等于 的排列数就是：枚举 的位置 ，在 个数中选 个放到左边且前面 个数的极大值在这 个数的最后 个之中（这样整个排列的极大值才会被覆盖成 ），后面任意排的方案

复杂度

Code

#include<bits/stdc++.h>
#define ll long long
#define FIO "cf886E"
#define mul3(a,b,c) mul(mul(a,b),c)
using namespace std;

const int N=1e6+5,MOD=1e9+7;

inline int add(int a,const int &b){return (a+=b)>=MOD?a-MOD:a;}
inline int sub(int a,const int &b){return (a-=b)<   0?a+MOD:a;}
inline int mul(const int &a,const int &b){return 1ll*a*b%MOD;}
inline int& inc(int &a,const int &b){return a=add(a,b);}
inline int& dec(int &a,const int &b){return a=sub(a,b);}
inline int& pro(int &a,const int &b){return a=mul(a,b);}
inline int qpow(int a,int b){int c=1;for(;b;b>>=1,pro(a,a))if(b&1)pro(c,a);return c;}
int fac[N],inv[N],invc[N];
inline int C(const int &a,const int &b){return mul3(fac[a],invc[b],invc[a-b]);}

int n,k,f[N],g[N],pre[N];

int main(){
  freopen(FIO".in","r",stdin);
  //freopen(FIO".out","w",stdout);

  fac[0]=fac[1]=inv[0]=inv[1]=invc[0]=invc[1]=1;
  for(int i=2;i<N;i++)
    fac[i]=mul(fac[i-1],i),inv[i]=mul(MOD-MOD/i,inv[MOD%i]),invc[i]=mul(invc[i-1],inv[i]);

  scanf("%d%d",&n,&k);
  f[0]=pre[0]=1;
  for(int i=1;i<=n;i++){
    f[i]=mul(fac[i-1],sub(pre[i-1],i>=k+1?pre[i-k-1]:0));
    pre[i]=add(pre[i-1],mul(f[i],invc[i]));
  }
  
  printf("%d\n",sub(fac[n],mul(fac[n-1],pre[n-1])));

  return 0;
}