Алпай очень любит математику. Особенно ему нравится возиться с выражениями, в которых много скобок. Ему попалась Олимпиадная задача, в которой надо было так расставить скобки, чтобы получилось нужное значение. Он хотел начать перебирать все варианты расстановок скобок, а потом задумался, а сколько же таких вариантов. Может для этого нужно несколько лет, а может быть и десятков и сотен лет. Помогите Алпаю узнать, сколько же имеется вариантов правильных расстановок N пар скобок
(открывающая и закрывающая скобки – одна пара).
Входные данные
Одно целое число N (1 <= N <= 35) – количество пар скобок.
Выходные данные
Единственное число – искомое количество вариантов.
Уровень сложности: 16/106 (85 %)
Пример входных данных
3
Пример выходных данных
5
это количество правильных ПСП из n открывающихся и закрывающихся скобок. Это можно посчитать динамикой d - ответ для i открывающихся и закрывающихся скобок d[0] = 1 for i in 1...n d = сумма всех d[k] * d[i - k - 1] для k = 0...i - 1