Алгоритмы и структуры данных

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

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

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

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

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

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

Примеры

Вход
Выход
1
2
2
2
3
4

Пояснение

  1. (red) (orange)
  1. (red, orange) (orange, red)
  1. (orange, red, orange) (red, blue, orange) (orange, blue, red) (red, orange, red)
 

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue