Уголки
Автор задачи: Сергей Штейнер
Задачу добавил: shtserg
Успешно сдано решений: 5
Дано натуральное число n, 1 <= n <= 109.
Необходимо вычислить количество замощений прямоугольника 3×n различными "уголками" из трёх клеток.
Ответ выдать по модулю числа 1000000007.
Пример 1
input.txt
1
output.txt
0
Пример 2
input.txt
2
output.txt
2
Замечание.
Решения, верно работающие для нечётных n, будут оцениваться не менее чем в 1 балл.
Решения, верно работающие при n <= 107, наберут не менее половины баллов.