Дистанционный практикум по программированию

Строка, состоящая из символов «(» и «)», называется скобочной последовательностью. Скобочная последовательность называется правильной, если она может быть получена из некоторого корректного арифметического выражения удалением всех символов, кроме скобок. Например, правильная скобочная последовательность «(())()» может быть получена из выражения «(2-(3+4)*6)*(1+1)».

Другое определение правильной скобочной последовательности можно дать следующим образом:

1.      Пустая строка является правильной скобочной последовательностью.

2.      Если S — правильная скобочная последовательность, то (S) — тоже правильная скобочная последовательность.

3.      Если S и T — правильные скобочные последовательности, то ST — правильная скобочная последовательность.

Глубиной правильной скобочной последовательности называется максимальная разность между количеством открывающихся и закрывающихся скобок в префиксе последовательности (префиксом строки S называется строка, которую можно получить из S удалением некоторого количества последних символов, например, префиксами строки «ABCAB» являются строки «», «A», «AB», «ABC», «ABCA» и «ABCAB»). Например, глубина последовательности «()()(())» равна двум (префикс «()()((» имеет 4 открывающиеся и 2 закрывающиеся скобки).

Требуется написать программу, определяющую по заданным значениям n и k количество правильных скобочных последовательностей с n открывающимися скобками, которые имеют глубину, равную k.

Формат входных данных

Входной файл содержит в одной строке целые числа n и k (1 ≤ k ≤ n ≤ 50), разделенные пробелом.

Формат выходных данных

Выходной файл должен содержать одно число — количество правильных скобочных последовательностей с n открывающимися скобками, которые имеют глубину k.

Примеры входных и выходных файлов

Входные данные	Выходные данные
3 2	3
37 23	203685956218528