Покраска с использованием цветов

Представьте, что вы хотите раскрасить полоску в три цвета — red, blue и orange. Каждый участок полосы окрашивается в один цвет. Чтобы сделать узор более заметным, вы решили придерживаться следующих правил:

1. Нельзя располагать одинаковые цвета рядом.

2. Цвет blue должен всегда находиться между red и orange или между orange и red.

Сколько различных вариантов раскрашивания можно получить, если вся полоска состоит из n участков?

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

Вход содержит одно целое число n (1 ≤ n ≤ ).

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

Программа должна вывести число различных раскрасок полоски. Поскольку это число может быть очень большим, выведите результат по модулю .

Примеры

Пояснение

1. (red) (orange)

2. (red, orange) (orange, red)

3. (orange, red, orange) (red, blue, orange) (orange, blue, red) (red, orange, red)