F. SubMST
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дано неориентированное невзвешенное дерево $$$T$$$ с $$$n$$$ вершинами.

Определим полный неориентированный взвешенный граф $$$G$$$ с $$$n$$$ вершинами, где вес ребра между вершинами $$$u$$$ и $$$v$$$ в $$$G$$$ равен расстоянию между этими вершинами в исходном дереве.

Для каждого возможного подмножества вершин рассмотрим минимальное остовное дерево (MST) подграфа $$$G$$$, образованное этим подмножеством. Требуется вычислить сумму весов MST для всех возможных подмножеств вершин графа G.

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

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10000$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка содержит целое число $$$n$$$ ($$$1 \leq n \leq 5000$$$) — число вершин в дереве.

Следующие $$$n-1$$$ строк содержат по два целых числа $$$u$$$ и $$$v$$$ ($$$1 \leq u,v \leq n$$$), задающих ребро между вершинами $$$u$$$ и $$$v$$$ в дереве.

Гарантируется, что сумма $$$n^2$$$ по всем наборам не превышает $$$5000^2$$$.

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

Выведите одно целое число — сумму весов MST для всех возможных подмножеств вершин по модулю $$$10^9+7$$$.

Пример
Входные данные
5
3
1 2
2 3
7
3 1
1 2
3 5
4 5
3 6
6 7
22
4 11
9 7
3 18
19 8
16 20
5 22
13 20
15 12
2 8
12 1
17 4
6 7
1 21
10 18
7 3
20 15
14 21
18 4
8 15
22 17
11 14
1
2
2 1
Выходные данные
6
496
74069416
0
1
Примечание

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