Matcom Online Grader

Para el próximo 10 de octubre Fito quiere decorar su casa usando los colores de la bandera (Rojo, Blanco y Azul).   Para esto va coser varios banderines de franjas usando estos colores. Para coser estos banderines tiene que seguir las condiciones siguientes:

1-      Dos franjas del mismo color no pueden ser colocados de manera adyacente.

2-      Las franjas rojas tiene que estar siempre entre una blanca y una azul o una azul y blanca.

Por lo que dadas la cantidad de franjas de la bandera que va a coser debe determinar la cantidad de posibles banderas que se pueden crear.

Por ejemplo para $N=3$ se pueden hacer:

Input

Línea 1 : La entrada consiste en un entero $N$ que representa la cantidad de franjas, $1 \le N \le 45$.

Output

Línea 1 : La cantidad de formas de crear diferentes banderas.

Sample test(s)