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.

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

Explicación

1. (red) (orange)

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

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