2015
09-17

# Round Table

I have m little buddies, and tonight we will have a fancy dinner in my room.
Fortunately, I have a round table which is large enough for all my little buddies. (As for me, I will not sit in the round table for some reasons) And the round table is so large that I will not let my little buddies sit shoulder to shoulder.
That means I will select m seats from n seats, and there maximal length of consecutive seats in the original round table won’t be larger than or equal to k. I want know how many different ways I can choose.
Here is one more thing, two ways are considered the same if and only if one can be obtained by rotation.

The answer may be very large so the answer should modulo 109 + 7.

The first line has a number T (T <= 200) , indicating the number of test cases.
Next each line contain three integer n, m, k (1 <= n <= 105, 1 <= m <= 105, 2 <= k <= 105, m <= n).

The first line has a number T (T <= 200) , indicating the number of test cases.
Next each line contain three integer n, m, k (1 <= n <= 105, 1 <= m <= 105, 2 <= k <= 105, m <= n).

3
3 1 2
5 2 2
8 3 2

Case #1: 1
Case #2: 1
Case #3: 2

Round Table
N个点成环,选择M个点,最长连续选取长度要小于K.

(1<=M<=N<=10^5,2<=K<=10^5)

Ans=∑_{u|gcd(n,M)}∑_{d|n/u}\miu[n/(ud)]*g(d)*u/n

//感谢叉姐告诉,b的我循环节的事情…