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

Найти количество правильных скобочных выражений длины N (), составленных из скобок M () типов.

 

Определение правильного скобочного выражения (на примере M=2 – круглые и квадратные скобки).

1. Пустое выражение правильное.

2. Если E – правильное выражение, то (E) и [E] – тоже правильные выражения.

3. Если E и F – правильные скобочные выражения, то EF – тоже.

 

Примеры правильных скобочных выражений:

()

[()]([[()]])[][[[(())]]]

Примеры неправильных скобочных выражений:

(

]

([)]

(][)

 

 

Во входном файле содержатся записанные через пробел числа N и M.

В выходной файл выводится одно число.

Примеры

STDIN	STDOUT
4 2	8
1 3	0