Задача I. (20081225) Б-деревья

Автор:Жюри зимних сборов 2009   Ограничение времени:5 сек
Входной файл:btrees.in   Ограничение памяти:64 Мб
Выходной файл:btrees.out  
Максимальный балл:100  

Условие

Если б дерево умело говорить...

Б-дерево — структура для хранения данных во вторичной памяти (например, на жёстком диске). Б-дерево обладает несколькими свойствами:

Обратите внимание, что корень может являться листом.

Два Б-дерева считаются различными, если они различны как графы с помеченными вершинами, или если вершина с одинаковыми пометками содержит различное количество ключей. Например, существует всего 8 различных Б-деревьев с четырьмя ключами и со степенью ветвления 2 (см. рисунок).

Посчитайте количество различных Б-деревьев с n ключами в листьях и степенью ветвления t.

Формат входного файла

В первой строке находятся два натуральных числа n и t — количество ключей в листьях и степень ветвления, соответственно (1 ≤ n ≤ 500, 2 ≤ t ≤ 109).

Формат выходного файла

В первой строке выведите единственное число без ведущих нулей — количество Б-деревьев с n ключами в листьях и степенью ветвления t.

Примеры тестов

Входной файл (btrees.in) Выходной файл (btrees.out)
1
4 2
8
2
20 2
17220826

0.095s 0.010s 15