Емблема центру  www.olymp.vinnica.ua     netoi.org.ua
Центр олімпіад школярів в Iнтернеті
Likt-PMG17
м.Вiнниця


Годинник
 
Trimino


Задача 
Trimino

Знайдіть кількість способів покриття прямокутника 4*N фігурками«Триміно». «Триміно» - це квадрат 2*2 з однією вирізаною клітинкою.


 

 

 

 

Технічні умови

Програма Trimino читає з клавіатури натуральне число N(1<=N<=100000) і виводить на екран шукану кількість способів за модулем 1000000007.

Приклади

Введення 3

Виведення 4

Введення 7

Виведення 0

Пояснення до першого прикладу. Усі способи покриття показано на малюнку.




© Всеукраїнський віртуальний центр олімпіад школярів "ОЛІМП"