1 // 排列组合+组合数取模 HDU 5894 2 // 题意：n个座位不同，m个人去坐(人是一样的)，每个人之间至少相隔k个座位问方案数 3 // 思路： 4 // 定好m个人 相邻人之间k个座位 剩下就剩n-(m+1)*k个座位 5 // 剩下座位去插m个不同的盒子==就等价n个相同的球放m个不同的盒子 6 // 然后组合数出来了 7 // 乘n的话是枚举座位，除m是去掉枚举第一个座位的时候，剩下人相邻的座位相对不变的情况 8  9 #include <iostream>10 #include <algorithm>11 #include <cstring>12 #include <cstdio>13 #include <vector>14 #include <cmath>15 #include <map>16 #include <queue>17 using namespace std;18 #define LL long long19 typedef pair<int,int> pii;20 const int inf = 0x3f3f3f3f;21 const int mod = 1e9+7;22 const int N = 1e6+10;23 const int maxx = 200010; 24 #define clc(a,b) memset(a,b,sizeof(a))25 const double eps = 1e-8;26 void fre() {freopen("in.txt","r",stdin);}27 void freout() {freopen("out.txt","w",stdout);}28 inline int read() {int x=0,f=1;char ch=getchar();while(ch>‘9‘||ch<‘0‘) {if(ch==‘-‘) f=-1; ch=getchar();}while(ch>=‘0‘&&ch<=‘9‘) {x=x*10+ch-‘0‘;ch=getchar();}return x*f;}29 30 int f[N];31 int inv(int x){32   int ret=1,y=mod-2;33   while(y){34     if(y&1)ret=1ll*ret*x%mod;35     y>>=1;x=1ll*x*x%mod;36   }37   return ret; 38 }39 int C(int n,int m){40   if(n<m)return 0;41   int ret=1ll*f[n]*inv(f[m])%mod;42   ret=1ll*ret*inv(f[n-m])%mod;43   return ret; 44 }45 int lucas(int n,int m){46    if(m == 0) return 1;47    return 1ll*C(n % mod, m % mod) * lucas(n / mod, m / mod) % mod;48 }49 50 void init(){51   f[0]=1;52   for(int i=1;i<=N-5;++i)f[i]=1ll*i*f[i-1]%mod;53 }54 55 int main(){56     init();57     int T;58     scanf("%d",&T);59     while(T--){60         int n,m,k;61         scanf("%d%d%d",&n,&m,&k);62         if(m==1){63             printf("%d\n",n);64             continue;65         }66         LL res=n-(m+1)*k;67         if(res<0){68             printf("0\n");69             continue;70         }71         LL tem=lucas(n-m*k-1,m-1);72         LL ans=((tem)%mod)*n%mod;73         printf("%d\n",(ans*inv(m))%mod);74     }75     return 0;76 }