Secuencias de 0’s

Las combinaciones de 0’s y 1’s de largo n, son por definición 2n. Así por ejemplo, si n es 3, las combinaciones diferentes son: 000, 001, 010, 011, 100, 101, 110, 111. En estas combinaciones existen unas que son muy especiales: aquellas que no tienen 0’s consecutivos. En el caso del ejemplo existen 5 combinaciones que no contemplan 0’s consecutivos que serian las combinaciones: 010, 011, 101, 110 y 111.

Tu tarea es decidir dado n cuántas combinaciones sin 0’s consecutivos existen.

Entrada

La entrada tiene varios casos de prueba. Cada caso de prueba consiste de una línea que tiene n (3 = n = 40) que es el largo de las combinaciones.

Salida

Para cada caso de prueba, la salida debe mostrar en una línea la cantidad de combinaciones que no tienen 0’s consecutivos.

Ejemplo de Entrada

3  
6  
4  
0

Ejemplo de Salida

5  
21  
8