Matcom Online Grader
Faculty of Mathematics and Computer Science of University of Havana

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)