Problem I
Powerbonacci
Languages
en
is
Sem síðasta dæmið um línuleg rakningavensl er Atli búinn að sjóða upp einhverja algjöra steypu. Hræðilega, ógeðslega rakningu. Allir elska Fibonacci-rununa, svo best er að algerlega rústa þeirri runu.
Látum $f_0 = 0$ og $f_1 = 1$ vera byrjunina á Fibonacci-rununni og skilgreinum svo hin gildin með $f_n = f_{n-1} + f_{n-2}$. Þá skilgreinum við $k$-tu Powerbonacci rununa $g_{k,0}, g_{k,1}, g_{k,2}, \dots $ með
\[ g_{k,n} = \sum _{i = 0}^n f_i^k \]Þú þarft nú að finna út úr því að vinna með þessa runu, gangi þér vel!
Inntak
Fyrsta og eina lína inntaksins inniheldur tvær jákvæðar heiltölur $n, k$ sem uppfylla $1 \leq n \leq 10^{18}$ og $1 \leq k \leq 1\, 000$.
Úttak
Prentið $g_{k,n}$. Þar sem þetta gildi gæti verið mjög stórt, prentið það mátað við $10^9 + 7$.
| Sample Input 1 | Sample Output 1 |
|---|---|
10 1 |
143 |
| Sample Input 2 | Sample Output 2 |
|---|---|
100 20 |
994581202 |
