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