Pixie is a very famous businessman who loves to give parties to his associates. One day he decided to organize a dinner like never before and gather all of his partners together. He asked a round table, so he can see everybody when he sits.
Pixie is a very friendly guy and has no restrictions on where he will sit. However, despite his contagious charisma, his partners only go to the the dinners on his account. In fact, they hate themselves so much (except for Pixie) that they fight if they sit close to each other. Consequently, they demand to sit apart at least R chairs from each other, so they can barely see their faces.
Pixie, a very curious man, would like to know in how many ways he can organize his partners in the table so there are no fights. However, he is too busy, and asks you to find this number for him.
You will receive the number N of chairs in the table (1 ≤ N ≤ 105), the number C of partners (1 ≤ C ≤ N) and the minimum number R of chairs that must be placed in the middle of every partner (1 ≤ R ≤ N). Help Pixie find out in how many ways he can organize his guests.
Three integers N, C and R, as described in the statement.
Print the number of ways to organize the guests at the table. As this number can be very large, print it modulo (109 + 7).
If it's not possible to place the guests at table respecting their restrictions, print - 1.
Two ways are distinct if the set of chairs occupied by the partners is distinct or if the chair in which Pixie sits is distinct.
## Input
Three integers N, C and R, as described in the statement.
## Output
Print the number of ways to organize the guests at the table. As this number can be very large, print it modulo (109 + 7).If it's not possible to place the guests at table respecting their restrictions, print - 1.
[samples]
## Note
Two ways are distinct if the set of chairs occupied by the partners is distinct or if the chair in which Pixie sits is distinct.
**Definitions**
Let $ N \in \mathbb{Z}^+ $ be the number of chairs arranged in a circle.
Let $ C \in \mathbb{Z}^+ $ be the number of partners to be seated.
Let $ R \in \mathbb{Z}^+ $ be the minimum number of chairs that must separate any two partners.
Let $ P $ denote Pixie, who occupies exactly one chair (distinct from partners).
**Constraints**
1. $ 1 \leq N \leq 10^5 $
2. $ 1 \leq C \leq N $
3. $ 1 \leq R \leq N $
4. Partners must be placed such that between any two adjacent partners (along the circle), there are **at least** $ R $ empty chairs.
5. Pixie occupies one chair; the remaining $ N - 1 $ chairs are for partners and empty seats.
6. Two configurations are distinct if either:
- The set of chairs occupied by partners differs, or
- Pixie’s chair differs.
**Objective**
Compute the number of valid ways to:
- Choose a chair for Pixie ($ N $ choices),
- Place $ C $ partners on the remaining $ N - 1 $ chairs such that any two partners are separated by **at least $ R $** empty chairs (along the circular arrangement),
modulo $ 10^9 + 7 $.
If no such arrangement exists, output $ -1 $.
**Note**: The circular constraint implies that the $ C $ partners must be placed with **at least $ R $** empty chairs between each consecutive pair (in cyclic order), so the total number of chairs required for partners and their mandatory gaps is at least $ C + C \cdot R = C(R + 1) $. Since Pixie occupies one chair, the remaining $ N - 1 $ chairs must accommodate $ C $ partners and $ \geq C \cdot R $ empty chairs as separators. Thus, a necessary condition is:
$$
C(R + 1) \leq N
$$
If this fails, return $ -1 $.
Otherwise, fix Pixie’s position (breaking rotational symmetry), and count the number of ways to choose $ C $ non-adjacent (with gap $ R $) positions among the remaining $ N - 1 $ linearized chairs (since Pixie breaks the circle).
Let $ M = N - 1 $. We now place $ C $ partners on a **line** of $ M $ chairs, such that any two are at least $ R + 1 $ positions apart (since $ R $ empty chairs between them → gap of $ R+1 $ indices).
This is equivalent to placing $ C $ objects with at least $ R $ gaps between them on a line of $ M $ positions.
Standard stars and bars:
Let $ x_i $ be the number of empty chairs before the first partner, between partners, and after the last.
We require:
- $ x_0 \geq 0 $
- $ x_i \geq R $ for $ i = 1, \dots, C-1 $
- $ x_C \geq 0 $
- $ \sum_{i=0}^{C} x_i = M - C $
Let $ y_i = x_i $ for $ i = 0, C $, and $ y_i = x_i - R $ for $ i = 1, \dots, C-1 $.
Then $ y_i \geq 0 $, and:
$$
\sum_{i=0}^{C} y_i = M - C - R(C - 1)
$$
Number of non-negative integer solutions:
$$
\binom{M - C - R(C - 1) + C}{C} = \binom{M - R(C - 1)}{C}
$$
provided $ M - R(C - 1) \geq C $, i.e., $ N - 1 - R(C - 1) \geq C $ → $ N \geq C(R + 1) $, as before.
Thus, for each of the $ N $ choices of Pixie’s seat, the number of valid partner arrangements is:
$$
\binom{N - 1 - R(C - 1)}{C}
$$
**if** $ N \geq C(R + 1) $, else $ 0 $.
But wait: **Is the arrangement invariant under rotation?** No — Pixie’s position is fixed and distinct. So we **do not** divide by symmetry. Each choice of Pixie’s chair gives a distinct configuration.
Therefore, total number of ways:
$$
\boxed{
\begin{cases}
N \cdot \dbinom{N - 1 - R(C - 1)}{C} \mod (10^9 + 7) & \text{if } N \geq C(R + 1) \\
-1 & \text{otherwise}
\end{cases}
}
$$