Problem H
Starbonacci
Languages
en
is
The Fibonacci numbers are quite famous and many might therefore recognise the sequence $1, 1, 2, 3, 5, 8, 13, 21, 34, \dots $. But fewer know the story of the sequence and why Fibonacci was investigating it. Not to mention that the fact that Fibonacci was far from the first one to consider it. Various Indian individuals had discovered this sequence before him, in particular finding it to be the number of ways to compose poems with a particular stress structure.
But back to Fibonacci. He was considering how rabbits reproduce over the course of several months. We will consider a similar model on rabbits. Suppose each rabbit lives for 3 years and each breeding pair has a pair of baby rabbits in their second and third year. We want to count the number of rabbits reaching adulthood each year.
Then if we start with a single pair in the first year, that pair will have offspring that mature on year two and three. But the offspring that mature in year two will have their own offspring maturing in year three. Therefore the number of rabbits reaching adulthood in year three is $2$. Similarly the fourth year will have $3$, then $5$ in year five and so on. The sequence we get is $1, 1, 2, 3, 5, \dots $. Here we count the original pair in the first year.
But what if we adjust the lifetime of a rabbit? What if a rabbit lives $4$ years and thus has offspring three times total? Or lives $m$ years? For example if $m = 5$ the sequence becomes $1, 1, 2, 4, 8, 15, 29, \dots $.
We want to consider this more general model and thus want to know for a given $m$ and given year $n$ the number of rabbits reaching adulthood that year. We consider the starting year to be year $1$, so if $m = 5$ and $n = 7$ the answer is $29$.
Input
The first line and only line of input contains two positive integers $n, m$, the number of the year to consider and the lifetime of the rabbits in years, as described above. You may assume that $1 \leq n \leq 10^{18}$ and $2 \leq m \leq 1\, 000$.
Output
Print the number of rabbits reaching maturity in year $n$ if rabbits live $m$ years, as described above. As the answer might be huge, print it modulo $10^9 + 7$.
| Sample Input 1 | Sample Output 1 |
|---|---|
7 5 |
29 |
| Sample Input 2 | Sample Output 2 |
|---|---|
12 3 |
144 |
| Sample Input 3 | Sample Output 3 |
|---|---|
1000 100 |
752264928 |
