D. Максимально распределенное дерево
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам задано дерево, состоящее из $$$n$$$ вершин. Вы должны сопоставить каждому из $$$n-1$$$ ребер этого дерева целое число таким образом, чтобы выполнялись следующие условия:

  • каждое число должно быть целым и строго больше $$$0$$$;
  • произведение всех $$$n-1$$$ чисел должно быть равно $$$k$$$;
  • количество $$$1$$$-ц среди всех $$$n-1$$$ чисел должно быть минимально возможным.

Назовем $$$f(u,v)$$$ сумму чисел на простом пути из вершины $$$u$$$ в вершину $$$v$$$. Также, назовем $$$\sum\limits_{i=1}^{n-1} \sum\limits_{j=i+1}^n f(i,j)$$$ как индекс распределения дерева.

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

В данной задаче, так как число $$$k$$$ может быть слишком большим, задана факторизация $$$k$$$ на простые числа.

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

В первой строке задано одно целое число $$$t$$$ ($$$1 \le t \le 100$$$) — количество наборов входных данных.

В первой строке каждого набора задано одно целое число $$$n$$$ ($$$2 \le n \le 10^5$$$) — количество вершин в дереве.

В каждой из следующих $$$n-1$$$ строк заданы ребра: в $$$i$$$-й строке заданы два целых числа $$$u_i$$$ и $$$v_i$$$ ($$$1 \le u_i, v_i \le n$$$; $$$u_i \ne v_i$$$) — номера вершин, соединенных $$$i$$$-м ребром.

В следующей строке задано одно число $$$m$$$ ($$$1 \le m \le 6 \cdot 10^4$$$) — количество простых в факторизации $$$k$$$.

В следующей строке заданы $$$m$$$ простых чисел $$$p_1, p_2, \ldots, p_m$$$ ($$$2 \le p_i < 6 \cdot 10^4$$$) такие, что $$$k = p_1 \cdot p_2 \cdot \ldots \cdot p_m$$$.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$10^5$$$, сумма $$$m$$$ по всем наборам не превосходит $$$6 \cdot 10^4$$$, и что заданные ребра в каждом наборе образуют дерево.

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

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

Пример
Входные данные
3
4
1 2
2 3
3 4
2
2 2
4
3 4
1 3
3 2
2
3 2
7
6 1
2 3
4 6
7 3
5 1
3 6
4
7 5 13 3
Выходные данные
17
18
286
Примечание

В первом наборе входных данных, один из возможных ответов изображен на рисунке ниже:

В данном случае, $$$f(1,2)=1$$$, $$$f(1,3)=3$$$, $$$f(1,4)=5$$$, $$$f(2,3)=2$$$, $$$f(2,4)=4$$$, $$$f(3,4)=2$$$, и сумма этих $$$6$$$ чисел равна $$$17$$$.

Во втором наборе входных данных, один из возможных ответов изображен ниже:

В этом случае, $$$f(1,2)=3$$$, $$$f(1,3)=1$$$, $$$f(1,4)=4$$$, $$$f(2,3)=2$$$, $$$f(2,4)=5$$$, $$$f(3,4)=3$$$, и сумма этих $$$6$$$ чисел равна $$$18$$$.