У Ксюши — сессия, сегодня она учит комбинаторику. Вот одна из задач, которую ей нужно научиться решать.
Сколько существует различных деревьев, состоящих из n вершин, каждое из которых обладает следующими свойствами:
- дерево — помеченное, то есть вершины дерева пронумерованы от 1 до n;
- каждая вершина дерева связана не более чем с тремя другими вершинами, при этом вершина с номером 1 связана не более чем с двумя другими вершинами;
- мощность максимального паросочетания дерева равна k.
Два дерева считаются различными, если существуют такие две вершины u и v, что в одном дереве они соединены ребром, а в другом — нет.
Помогите Ксюше решить задачу для заданных n и k. Так как ответ может быть достаточно большим, выведите его по модулю 1000000007 (109 + 7).