{"raw_statement":[{"iden":"statement","content":"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.\n\nPixie 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.\n\nPixie, 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.\n\nYou 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.\n\nThree integers N, C and R, as described in the statement.\n\nPrint the number of ways to organize the guests at the table. As this number can be very large, print it modulo (109 + 7).\n\nIf it's not possible to place the guests at table respecting their restrictions, print  - 1.\n\nTwo ways are distinct if the set of chairs occupied by the partners is distinct or if the chair in which Pixie sits is distinct.\n\n"},{"iden":"input","content":"Three integers N, C and R, as described in the statement."},{"iden":"output","content":"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."},{"iden":"examples","content":"Input9 3 2Output18Input10 2 1Output280"},{"iden":"note","content":"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."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ N \\in \\mathbb{Z}^+ $ be the number of chairs arranged in a circle.  \nLet $ C \\in \\mathbb{Z}^+ $ be the number of partners to be seated.  \nLet $ R \\in \\mathbb{Z}^+ $ be the minimum number of chairs that must separate any two partners.  \n\nLet $ P $ denote Pixie, who occupies exactly one chair (distinct from partners).  \n\n**Constraints**  \n1. $ 1 \\leq N \\leq 10^5 $  \n2. $ 1 \\leq C \\leq N $  \n3. $ 1 \\leq R \\leq N $  \n4. Partners must be placed such that between any two adjacent partners (along the circle), there are **at least** $ R $ empty chairs.  \n5. Pixie occupies one chair; the remaining $ N - 1 $ chairs are for partners and empty seats.  \n6. Two configurations are distinct if either:  \n   - The set of chairs occupied by partners differs, or  \n   - Pixie’s chair differs.  \n\n**Objective**  \nCompute the number of valid ways to:  \n- Choose a chair for Pixie ($ N $ choices),  \n- 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),  \n\nmodulo $ 10^9 + 7 $.  \n\nIf no such arrangement exists, output $ -1 $.  \n\n**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:  \n$$\nC(R + 1) \\leq N\n$$  \nIf this fails, return $ -1 $.  \n\nOtherwise, 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).  \n\nLet $ 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).  \n\nThis is equivalent to placing $ C $ objects with at least $ R $ gaps between them on a line of $ M $ positions.  \n\nStandard stars and bars:  \nLet $ x_i $ be the number of empty chairs before the first partner, between partners, and after the last.  \nWe require:  \n- $ x_0 \\geq 0 $  \n- $ x_i \\geq R $ for $ i = 1, \\dots, C-1 $  \n- $ x_C \\geq 0 $  \n- $ \\sum_{i=0}^{C} x_i = M - C $  \n\nLet $ y_i = x_i $ for $ i = 0, C $, and $ y_i = x_i - R $ for $ i = 1, \\dots, C-1 $.  \nThen $ y_i \\geq 0 $, and:  \n$$\n\\sum_{i=0}^{C} y_i = M - C - R(C - 1)\n$$  \nNumber of non-negative integer solutions:  \n$$\n\\binom{M - C - R(C - 1) + C}{C} = \\binom{M - R(C - 1)}{C}\n$$  \nprovided $ M - R(C - 1) \\geq C $, i.e., $ N - 1 - R(C - 1) \\geq C $ → $ N \\geq C(R + 1) $, as before.  \n\nThus, for each of the $ N $ choices of Pixie’s seat, the number of valid partner arrangements is:  \n$$\n\\binom{N - 1 - R(C - 1)}{C}\n$$  \n**if** $ N \\geq C(R + 1) $, else $ 0 $.  \n\nBut 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.  \n\nTherefore, total number of ways:  \n$$\n\\boxed{\n\\begin{cases}\nN \\cdot \\dbinom{N - 1 - R(C - 1)}{C} \\mod (10^9 + 7) & \\text{if } N \\geq C(R + 1) \\\\\n-1 & \\text{otherwise}\n\\end{cases}\n}\n$$","simple_statement":"You are given a round table with N chairs. You need to seat C partners such that any two partners are at least R chairs apart (measured along the table). Pixie sits at one chair and is not counted among the C partners. Count the number of ways to choose chairs for the partners and decide where Pixie sits. If impossible, return -1. Answer modulo 10^9+7.","has_page_source":false}