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.

2. 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

Explicação

1. (red) (orange)

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

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