Algoritmos e Estruturas de Dados

Pintar com cores

Gostaria de pintar uma faixa com 3 cores — red, blue e orange. Cada unidade da faixa deve ser pintada com apenas uma cor. Para deixá-la mais chamativa, decidiu seguir estas regras:
  1. Não pode colocar a mesma cor lado a lado.
  1. A cor blue deve estar sempre posicionada entre red e orange ou entre orange e red.
Quantas faixas diferentes pode obter se a faixa tiver n unidades no total?

Entrada

A entrada contém um único inteiro n (1 ≤ n ≤ ).

Saída

O programa deve imprimir o número de faixas diferentes que podem ser obtidas. Como a resposta pode ser muito grande, deve ser impressa com o módulo .

Exemplos

Entrada
Saída
1
2
2
2
3
4

Explicação

  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