404770: GYM101628 G Get away from me!
Description
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.
InputThree integers N, C and R, as described in the statement.
OutputPrint 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.
ExamplesInput9 3 2Output
18Input
10 2 1Output
280Note
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.