Задача Trimino

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

 

 

 

 

 

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

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

Приклади

Введення 3

Виведення 4

Введення 7

Виведення 0

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

 


© LIKT 1998-2018