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.
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.
Para cada caso de prueba, la salida debe mostrar en una línea la cantidad de combinaciones que no tienen 0’s consecutivos.
3 6 4 0
5 21 8