Hero is preparing a party for his friends. He has a round table with N seats. The seats are numbered 0 through N-1, in order. In other words, seats with consecutive numbers are adjacent, and seat N-1 is adjacent to seat 0.
Hero knows that exactly K friends will attend the party, and that each of them will arrive at a different time. Each time a new friend arrives, Hero has to assign him (or her) one of the empty seats at the table. The friend then sits there for the rest of the party. Hero is not sitting at the table.
For the purpose of this problem, a cluster is a maximal group of people that occupy consecutive chairs. For example, if there are people on chairs 3, 4, 5, and 6, while chairs 2 and 7 are empty, then these four people form a cluster.
At a party, clusters are good: people who sit in a cluster can talk to each other and have fun. A party with too many clusters is bad. Therefore, Hero wants to make sure that at no point in time are there more than G clusters at his table.
For example, let N = 4 and K = 3. That is, we have a table with four seats, and three friends are going to arrive. We will use A, B, and C to denote the three friends (in the order in which they arrive) and a period ('.') to denote an empty chair. So, for example, "ABC." denotes that A got seat 0, B seat 1, C seat 2, and seat 3 remained empty. The configurations ".ABC" and "C.AB" are considered different from "ABC." and from each other: the friends sit in the same order but on different seats.
Continuing our example, let G = 1. That is, we must never have more than one cluster. This constraint restricts the set of possible final configurations. For example, "ABC.", "C.AB", "B.CA", and ".BAC" are all possible, but "A.BC" and ".ACB" are not. (Note that if the final configuration were "A.BC", then the configuration before C arrived was "A.B.", which means that there was more than one cluster at that point in time.)
You are given the ints N, K, and G. Count the number of possible final configurations. Return that count modulo 1,000,000,007. | 
