Genera todas las secuencias de \(n\) pares de paréntesis bien balanceadas: cada ( se cierra con un ) posterior y ningún prefijo tiene más ) que (.

Entrada

Un entero \(n\) \((1 \le n \le 8)\).

Salida

La primera línea tiene la cantidad de secuencias. Siguen las secuencias, una por línea, en orden lexicográfico (( va antes que )).

Ejemplo 1

Entrada

3

Salida

5
((()))
(()())
(())()
()(())
()()()

Ejemplo 2

Entrada

1

Salida

1
()