G. Владислав и великая легенда
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Однажды здесь была великая легенда, но один тролль взломал Codeforces и удалил его. Очень плохо для наc, но в сообществе троллей он заработал уважение и титул овер-супер-мега тролля. Пожалуй для них это что-то хорошее. А для нас, наверное, ещё лучше будет формальное условие.

Вам дано дерево $$$T$$$, содержащее $$$n$$$ вершин, пронумерованных от $$$1$$$ до $$$n$$$. Для каждого непустого $$$X$$$, являющемся подмножеством вершин $$$T$$$, определим $$$f(X)$$$ как количество рёбер в минимальном по размеру поддереве $$$T$$$, содержащем все вершины из $$$X$$$.

Вам также дано целое число $$$k$$$. Вам нужно вычислить сумму $$$(f(X))^k$$$ по всем непустым подмножествам вершин, то есть:

$$$$$$ \sum\limits_{X \subseteq \{1, 2,\: \dots \:, n\},\, X \neq \varnothing} (f(X))^k. $$$$$$

Так как эта величина может быть очень большой, выведите её по модулю $$$10^9 + 7$$$.

Входные данные

Первая строка содержит два целых числа $$$n$$$ и $$$k$$$ ($$$2 \leq n \leq 10^5$$$, $$$1 \leq k \leq 200$$$) — размер дерева и степень при суммировании.

Каждая из следующих $$$n - 1$$$ строк содержит два целых числа $$$a_i$$$ и $$$b_i$$$ ($$$1 \leq a_i,b_i \leq n$$$) — индексы вершин, соединённых соответствующим ребром.

Гарантируется, что заданные рёбра образуют дерево.

Выходные данные

Выведите одно целое число — требуемую сумму по модулю $$$10^9 + 7$$$.

Примеры
Входные данные
4 1
1 2
2 3
2 4
Выходные данные
21
Входные данные
4 2
1 2
2 3
2 4
Выходные данные
45
Входные данные
5 3
1 2
2 3
3 4
4 5
Выходные данные
780
Примечание

В первых двух примерах значения $$$f$$$ выглядят следующим образом:

$$$f(\{1\}) = 0$$$

$$$f(\{2\}) = 0$$$

$$$f(\{1, 2\}) = 1$$$

$$$f(\{3\}) = 0$$$

$$$f(\{1, 3\}) = 2$$$

$$$f(\{2, 3\}) = 1$$$

$$$f(\{1, 2, 3\}) = 2$$$

$$$f(\{4\}) = 0$$$

$$$f(\{1, 4\}) = 2$$$

$$$f(\{2, 4\}) = 1$$$

$$$f(\{1, 2, 4\}) = 2$$$

$$$f(\{3, 4\}) = 2$$$

$$$f(\{1, 3, 4\}) = 3$$$

$$$f(\{2, 3, 4\}) = 2$$$

$$$f(\{1, 2, 3, 4\}) = 3$$$