Problem H
Starbonacci

Fibonacci tölurnar eru ansi frægar og margir kannast því rununa $ 1, 1, 2, 3, 5, 8, 13, 21, 34, \dots $. En færri þekkja sögu talnarununnar, eins og hvers vegna Fibonacci var að skoða þær. Utan við það að Fibonacci var langt um fyrstur til að skoða rununa. Þónokkrir ólíkir indverskir fræðimenn voru búnir að uppgötva þessa runu við það að reyna að telja fjölda ljóða sem fylgja tilteknum atkvæðaáherslureglum.

En aftur að Fibonacci. Hann var að skoða hvernig kanínum fjölgar milli mánaða. Við munum skoða hliðstætt verkefni um kanínur. Hugsum okkur sem svo að hvert par af kanínum lifir í þrjú ár og eignast pör sem verða þroskuð á öðru og þriðja ári. Við viljum telja hvað það þroskast margar kanínur hvert ár.

Þá ef við byrjum með eitt par á fyrst ári mun það par eignast par sem verður fullorðið á öðru og þriðja ári. En parið sem varð fullorðið á öðru ári mun eiga sitt eigið fyrsta par sem verður fullorðið á þriðja ári, svo á þriðja ári þroskuðust tvö pör af kanínum. Eins mun sjást að á fjórða ári þroskast 3, svo á fimmta ári 5 og svo framvegis. Runan okkar verður $1, 1, 2, 3, 5, \dots $. Við teljum hér upprunalega parið með á fyrsta árinu.

En hvað ef við breytum hvað hver kanína lifir lengi? Hvað ef hver kanína lifir $4$ ár og eignast þá börn þrjú ár í röð? En $m$ ár? Til dæmis ef $m = 5$ verður runan $1, 1, 2, 4, 8, 15, 29, \dots $.

Við viljum skoða þetta almennara líkan og viljum því vita fyrir gefið $m$ og gefið ár $n$ hversu margar kanínur þroskast það ár. Hér lítum við á sem svo að fyrst árið sé ár $1$, svo ef $m = 5$ og $n = 7$ ætti svarið að vera $29$.

Inntak

Fyrsta og eina lína inntaksins inniheldur tvær jákvæðar heiltölur $n, m$, ársnúmer og líftíma kanína í árum eins og lýst er að ofan. Gefið er að $1 \leq n \leq 10^{18}$ og $2 \leq m \leq 1\, 000$.

Úttak

Prentið fjölda kanínupara sem þroskast ár $n$ ef hvert par lifir $m$ ár, eins og lýst er að ofan. Þar sem svarið gæti orðið mjög stórt skal skila því mátað við $10^9 + 7$.

7 5

29

12 3

144

1000 100

752264928