Question v: hannnnah_ j’s Biological Test

Problem Description

hannnnah_j is a teacher in WL High school who teaches biology.

One day, she wants to test m students, thus she arranges n different seats around a round table.

In order to prevent cheating, she thinks that there should be at least k empty seats between every two students.

hannnnah_j is poor at math, and she wants to know the sum of the solutions.So she turns to you for help.Can you help her? The answer maybe large, and you need to mod 1e9+7.

 

Input

First line is an integer T(T≤1000).
The next T lines were given n, m, k, respectively.
0 < m < n < 1e6, 0 < k < 1000

 

Output

For each test case the output is only one integer number ans in a line.

 

Sample Input

2 4 2 6 5 2 1

 

Sample Output

0 5

 

Source

2016 ACM/ICPC Asia Regional Shenyang Online

#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;
long long n,m,p,k;
long long quickpow(long long base,long long power){
   long long ret=1;
   while(power){
      if(power%2)
         ret=ret*base%p;
      base=base*base%p;
      power/=2;
   }
   return ret;
}
long long C(long long n,long long m){
    if(n<m)      return 0;
	if(m>n-m)     m=n-m;
	long long  a=1,b=1;
	for(int i=0;i<m;i++){
		a=(a*(n-i))%p;
		b=(b*(i+1))%p;
	}
	return a*quickpow(b,p-2)%p;
}
long long Lucas(long long n,long long m){
    if(m==0)  return 1;
    return Lucas(n/p,m/p)*C(n%p,m%p)%p;
}
int main()
{
    p=1e9+7;
    int T;
    scanf("%d",&T);
    while(T--){
        scanf("%lld%lld%lld",&n,&m,&k);
        if(m==1)
        {
            printf("%lld\n",n);
        }
        else
        printf("%lld\n",n*Lucas(n-k*m-1,m-1)%p*quickpow(m,p-2)%p);
    }
    return 0;
}