Задачи
Флаги
Флаги
Флаг состоит из n вертикальных полос белого, красного и синего цвета. Соседние полосы не могут иметь одинаковый цвет, а синяя полоса всегда должна находиться между красной и белой. Сколькими способами можно покрасить флаг из n полос?
Входные данные
Число полос n (1 ≤ n ≤ 10^6
) на флаге.
Выходные данные
Выведите количество способов, которыми можно покрасить флаг из n полос. Ответ выведите по модулю 10^9
+ 7.
Пример
Входные данные #1
3
Выходные данные #1
4