Contest.uni-smr.ac.ru :: соревнования по программированию
Русская версия || English version
Login:
Password:
Забыли пароль?
 пример поиска: Вася Пупкин
 






Уголки

Автор задачи: Сергей Штейнер

Задачу добавил: 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, наберут не менее половины баллов.

Сдать задачу

Задать вопрос жюри по этой задаче