Escribiendo paréntesis P82409

Los Milabs son los habitantes del planeta Milab. Estos bichos tienen un cerebro altamente desarrollado. Por contra, sus prehistóricas cuerdas vocales están muy limitadas, cosa que les obligó a desarrollar el curioso lenguaje Nuxaeron.

El alfabeto del Nuxaeron es binario. Sin embargo, en vez de escribir con ceros y unos, (como todo buen programador haría) escriben con paréntesis. En principio, se pueden formar $2^k$ palabras de longitud $k$, puesto que cada carácter puede ser ‘(’ (pronúnciese “uhng”) o bien ‘)’ (pronúnciese “uhhhn”). Pero aunque sean tan inteligentes, los Milabs son tan vagos como los habitantes de la Tierra, (o “()()(()(()))”, como ellos la llaman) y no quieren memorizar demasiadas palabras distintas. Por lo tanto, han establecido una norma: sólo pueden decir palabras bien parentizadas, o sea, pueden decir “()” o “(()())”, pero no pueden decir “())(” ni “)(”. Por ejemplo, éstas son las 5 palabras correctas de longitud 6: $$((())) \quad ()(()) \quad (())() \quad (()()) \quad ()()()$$ Para hablar bien Nuxaeron, deberéis determinar cuantas palabras correctas de longitud $n$ existen.

Entrada

La entrada consiste en diversos naturales $n$ entre 1 y 67.

Salida

Para cada $n$, escribid la cantidad de palabras correctas en Nuxaeron de ese tamaño.

Observación

Si no conocéis qué son los números de Catalan, éste es un buen momento para aprenderlo.