eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Флаги

Флаги

Лимит времени 1 секунда
Лимит использования памяти 128 MiB

Флаг состоит из n вертикальных полос белого, красного и синего цвета. Соседние полосы не могут иметь одинаковый цвет, а синяя полоса всегда должна находиться между красной и белой. Сколькими способами можно покрасить флаг из n полос?

Входные данные

Число полос n (1n10^6) на флаге.

Выходные данные

Выведите количество способов, которыми можно покрасить флаг из n полос. Ответ выведите по модулю 10^9 + 7.

Пример

Входные данные #1
3
Выходные данные #1
4