У Ксюши — сессия, сегодня она учит комбинаторику. Вот одна из задач, которую ей нужно научиться решать.
Сколько существует различных деревьев, состоящих из n вершин, каждое из которых обладает следующими свойствами:
- дерево — помеченное, то есть вершины дерева пронумерованы от 1 до n;
- каждая вершина дерева связана не более чем с тремя другими вершинами, при этом вершина с номером 1 связана не более чем с двумя другими вершинами;
- мощность максимального паросочетания дерева равна k.
Два дерева считаются различными, если существуют такие две вершины u и v, что в одном дереве они соединены ребром, а в другом — нет.
Помогите Ксюше решить задачу для заданных n и k. Так как ответ может быть достаточно большим, выведите его по модулю 1000000007 (109 + 7).
Выходные данные
Выведите единственное целое число — ответ на задачу по модулю 1000000007 (109 + 7).
Примечание
Если вы не знакомы с понятием максимальное паросочетание, почитайте статью по ссылке: http://ru.wikipedia.org/wiki/Паросочетание.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
1 1
|
0
|
|
2
|
2 1
|
1
|
|
3
|
3 1
|
3
|
|
4
|
4 2
|
12
|