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

Вхідні дані

Число смужок n (1 ≤ n ≤ 106) на стязі.

Вихідні дані

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