Скобки разных видов

Сколько существует правильных скобочных последовательностей из $n$ пар скобок, если скобки бывают $k$ различных видов?

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

Одна строка: числа $n$ от $0$ до $500$ и $k$ от $1$ до $100$.

Одно число.

Сначала посчитайте, сколько правильных последовательностей из одинаковых скобок. Затем заметьте, что вид каждой из $n$ пар выбирается независимо.