Remote Training on Programming

Если из корректно записанного арифметического выражения, содержащего числа, знаки операций и открывающие и закрывающие круглые скобки, выбросим числа и знаки операций, а затем запишем оставшиеся в выражении скобки без пробелов между ними, то полученный результат назовем правильным скобочным выражением. Например, скобочное выражение "(()(()))" - правильное, а "()(" и "())(" - нет.

Получите все правильные скобочные выражения, содержащие N открывающих и N закрывающих скобок.

Входные данные: число N, 0<N<=12

Выходные данные: в первой строке количество K правильных скобочных выражений, в следующих K строках – правильные скобочные выражения.

Пример входных данных:

3

Пример результата:

5

((()))

()(())

(())()

()()()

(()())