Laiko ribojimas: 1s

Atminties ribojimas: 64MB

Jei norite pateikti savo sprendimą - prisijunkite.

Lenta 2

Gintarė turi 2\\timesn lentą, ant kurios gali dėlioti 1\\times2 ir 2\\times2 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ų Gintarei 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škinimas 
3
 
5
 
Yra penki variantai, kaip Gintarė galėtų uždengti kaladėlėmis lentą, kurios matmenys 2\\times3:
pavyzdys