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

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

Число полос n (1 ≤ n ≤ 106) на флаге.

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

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