Problem I
Powerbonacci
Languages
en
is
As a final problem in the set of linear recurrences, Atli has cooked up the worst possible problem about them. Nastiest, worstest sequence imaginable. Everyone loves the Fibonacci sequence of course, so it is best to absolutely ruin that sequence.
We let $f_0 = 0$ and $f_1 = 1$ be the start of the Fibonacci sequence and for further entries let $f_n = f_{n-1} + f_{n-2}$. Then we can define the $k$-th Powerbonacci sequence $g_{k,0}, g_{k,1}, g_{k,2}, \dots $ by
\[ g_{k,n} = \sum _{i = 0}^n f_i^k \]You now have to work with this sequence, good luck!
Input
The first and only line of input contains two positive integers $n, k$ satisfying $1 \leq n \leq 10^{18}$ and $1 \leq k \leq 1\, 000$.
Output
Print $g_{k,n}$. Because this value might be very big, print it modulo $10^9 + 7$.
| Sample Input 1 | Sample Output 1 |
|---|---|
10 1 |
143 |
| Sample Input 2 | Sample Output 2 |
|---|---|
100 20 |
994581202 |
