Задача Trimino
Знайдіть кількість способів покриття прямокутника 4*N фігурками«Триміно». «Триміно» - це квадрат 2*2 з однією вирізаною клітинкою.
|
|
|
|
|
|
Технічні умови
Програма Trimino читає з клавіатури натуральне число N(1<=N<=100000) і виводить на екран шукану кількість способів за модулем 1000000007.
Приклади
Введення 3
Виведення 4
Введення 7
Виведення 0
Пояснення до першого прикладу. Усі способи покриття показано на малюнку.
