Nosaukums
Fibonači virkne (fibonaci_virkne)
Laika limits
0.50s
Atmiņas limits
32.0 MB
Grūtība
78%

Definīcija

Fibonači (1170-1250) dzīvoja Pizas republikā (mūsdienu Itālijā) un tiek uzskatīts par vistalantīgāko viduslaiku matemātiķi. Viņš iepazītināja Eiropu ar Fibonači skaitļiem un arī mūsdienu programmētājiem vajadzētu par tiem zināt. Pirmais Fibonačī virknes elements ir 0 un otrais elements ir 1. Katrs nākamais Fibonači skaitlis ir divu iepriekšejo virknes elementu summa. Ja kvadrātus ar Fibonačī skaitļu malu garumiem liek vienu otram blakus, iegūstam Fibonači spirāli. Tā līdzinās Zelta griezumam, bet Fibonāči spirāle NAV Zelta griezums... :/

Jevgēnijs ir programmētājs ar pieredzi un standarta Fibonačī skaitļu virknes viņu vairs neaizrauj. Viņu neapmierina  fakts, ka jāsaskaitā tikai divi skaitļi, lai iegūtu nākamo elementu (.-.). Jevgēnija Fibonači virknes nākamo elementu veido k iepriekšējo skaitļu summa. Arī viņa virknē pirmie divi elementi ir 0 un 1. Ja pašreizējā virknē ir mazāk par k elementiem, tad trūkstošie elementi tiek aizstāti ar 0.

Lai aizpildītu ziemas tumšos vakarus, Jevgēnijs ir izlēmis sākt gleznot. Viņš grib pārspēt Marku Rotko un ticams, ka pavisam drīz daudzu biroju sienas rotās Jevgēnija gleznas un to kopijas. Matemātiskā māksla viņu piesaista visvairāk, tāpēc viņš glezno kvadrātus, kuru malu garums ir n-tais Jevgēnija Fibonači virknes skaitlis. Jevgēnija audekls nav bezgalīgi liels, tāpēc jebkurš skaitlis ir dalīšanas atlikums ar 109 (desmit devītajā pakāpē). Palīdzi Jevgēnijam radīt mākslu un atrod n-to skaitli Jevgēnija Fibonači virknē.


Ievaddatu raksturojums

Doti divi veseli skaitļi n un k (1 ≤ n ≤ 100, 2 ≤ k ≤ 100).


Izvaddatu raksturojums

Izvadīt n-to skaitli Jevgēnija Fibonači skaitļu virknē. Ja skaitlis ir lielāks par 109, izvadīt atlikumu no dalīšanas ar 109.


Piezīmes

5 punktus var iegūt ar k ≤ 3.


Paraugdati

Stdin
4 5
Stdout
2

Uzdevums tiek aizsargāts ar autortiesībām un tā kopēšana vai neatļauta izmantošana ir aizliegta.