Задача Trimino

Найдите количество способов покрытия прямоугольника 4*N фигурками «Тримино». «Тримино» - это квадрат2*2 с одной вырезанной клеточкой.

Технические условия

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

Примеры 

Ввод 3

Вывод 4

Ввод 7

Вывод 0

Комментарий к первому примеру: все способы покрытия указаны на рисунке.