Algoritmos y Estructuras de Datos

Pintar con colores

Te gustaría pintar una franja utilizando 3 colores: red, blue y orange. Cada unidad de la franja se pinta con un solo color. Para que resulte más llamativa, has decidido seguir estas reglas:
  1. No se pueden colocar los mismos colores uno al lado del otro.
  1. El color blue siempre debe ubicarse entre red y orange o entre orange y red.
La pregunta es: ¿cuántas franjas diferentes se pueden obtener si la franja completa tiene n unidades?

Entrada

La entrada contiene un único entero n (1 ≤ n ≤ ).

Salida

El programa debe imprimir la cantidad de franjas diferentes que se pueden obtener. Dado que el resultado puede llegar a ser muy grande, se debe imprimir el resultado módulo .

Ejemplos

Entrada
Salida
1
2
2
2
3
4

Explicación

  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