Fişierul intrare/ieşire:	recurenta.in, recurenta.out	Sursă	Algoritmiada 2009, Runda 3
Autor	Stefan Alexandru Filip	Adăugată de	Stefan-Alexandru Filip •Prostu
Timp execuţie pe test	0.15 sec	Limită de memorie	20480 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Recurenta

Dubota a invatat la scoala despre numerele Fibonacci. Aceste numere sunt definite in felul urmator: primii termeni ai sirului sunt 0, F₀ = F₁ = 1, iar al n-lea termen, 2 ≤ n, se obtine adunand termenii n-1 si n-2 ai sirului F_n = F_n-1 + F_n-2. Acum Dubota este curios care sunt termenii sirurilor ai caror termeni se obtin adunand ultimii k termeni si au primii k termeni egali cu 1. D₀ = D₁ = ... = D_k-1 = 1, D_n = D_n-1 + D_n-2 + ... + D_n-k, k ≤ n. Fiind dat k, Dubota va cere sa ii spuneti care este termenul de indice n al sirului care se formeaza prin regula prezentata mai sus.

Date de intrare

Fişierul de intrare recurenta.in va contine doua numere separate prin spatiu, n si k cu semnificatia din enunt.

Date de ieşire

În fişierul de ieşire recurenta.out va contine un singur numar, termenul de indice n al sirului.

Restricţii

• k ≤ n ≤ 10000
• 2 ≤ k ≤ 1000

Exemplu

Explicaţie

D₀ = D₁ = D₂ = 1, D₃ = 3, D₄ = 5, D₅ = 9, D₆ = 17.

Cum se trimit solutii?