Правильной скобочной последовательностью (ПСП) называется строка, состоящая только из круглых скобок, где каждой закрывающей скобке найдётся соответствующая открывающая, и наоборот. Примеры ПСП: '()', '(())', '()(())'. Примеры строк, не являющихся ПСП: '())', ')(', '(()'.
Назовём ПСП длины $$$2n$$$ симметричной, если для любого $$$i$$$ от $$$1$$$ до $$$n$$$ верно, что $$$i$$$-я скобка с начала не равна $$$i$$$-й скобке с конца. Например, для $$$n=3$$$ следующие ПСП являются симметричными: '((()))', '()()()' и '(()())'.
Напишите программу, вычисляющую количество симметричных ПСП длины $$$2n$$$.
Вводится одно целое число $$$n$$$ ($$$1 \le n \le 50$$$).
Выведите одно целое число — количество симметричных ПСП длины $$$2n$$$.
Подзадача 1 (до 45 баллов): $$$n \le 10$$$
Подзадача 2 (до 25 баллов): $$$n \le 20$$$
Подзадача 3 (до 30 баллов): $$$n \le 50$$$
3
3
Обратите внимание, что ответ в последней подзадаче может быть достаточно большим и не помещаться в 32-битный тип данных. Рекомендуется использовать 64-битный тип данных, например, тип long long в языке C++, тип int64 в языке Pascal, тип long в языках Java и C#. Язык Python автоматически работает с целыми числами любой длины.
