Laiko ribojimas: 1s

Atminties ribojimas: 64MB

Jei norite pateikti savo sprendimą - prisijunkite.

Lenta 1

Povilas turi 1\\timesn lentą, ant kurios gali dėlioti 1\\times1, 1\\times2 arba 1\\times3 kaladėles. Jis jas dėlioja taip, kad kaladėlės nesikirstų viena su kita, neišlįstų už lentos ribų ir kad neliktų lentoje tuščių tarpų.

Raskite, kiek yra būdų Povilui uždengti lentą kaladėlėmis.

Pradiniai duomenys

Pateikiamas vienas natūralusis skaičius n (1\\leqn\\leq10^6).

Rezultatai

Išveskite atsakymo liekaną dalinant iš 10^9+7.

Pavyzdys

Duomenys Rezultatai Paaiškinimai
4
7
Yra septyni variantai, kaip Povilas galėtų uždengti kaladėlėmis lentą, kurios matmenys 1\\times4:
pavyzdys