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 10⁹ (desmit devītajā pakāpē). Palīdzi Jevgēnijam radīt mākslu un atrod n-to skaitli Jevgēnija Fibonači virknē.

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

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

5 punktus var iegūt ar k ≤ 3.