В любой стратегической игре, и в «Цивилизации» в том числе, есть множество скиллов (навыков), которые игрок может изучить и приобрести.
Каждый из $$$n$$$ навыков в «Цивилизации» обладает типом — военный, культурный, строительный, и так далее. Будем обозначать тип $$$i$$$-го навыка целым числом $$$c_i$$$. Также навыки упорядочены в подвешенное дерево — у каждого навыка есть один предшествующий ему, который необходимо изучить, чтобы получить к нему доступ. Процесс изучения навыков начинается с корня дерева — с базового навыка, изучение которого напрямую или косвенно необходимо для открытия всех остальных.
Скажем, что два навыка $$$u$$$ и $$$v$$$ похожи, если мультимножества типов навыков в их поддеревьях совпадают. Иными словами, чтобы два навыка были похожи, необходимо, чтобы в их поддеревьях было поровну навыков каждого типа.
«Цивилизация VII» еще не вышла, и разработчики проверяют различные гипотезы о том, как дерево навыков должно выглядеть. Для этого они $$$q$$$ раз выполняют переподвешивание дерева за другую вершину и вычисляют число пар похожих навыков. При переподвешивании дерева за навык $$$v$$$ он становится корневым (самым первым для изучения), а все остальные ребра дерева сохраняются, но на каких-то из них соответствующим образом меняется направление того, какой навык от какого зависит.
Для каждого из $$$q$$$ запросов переподвешивания дерева посчитайте количество неупорядоченных пар похожих навыков после выполнения запроса. «Неупорядоченные пары» означает, что пара $$$(u, v)$$$ и пара $$$(v, u)$$$ считаются за одну. Поскольку ответ может быть большим, выведите его остаток по модулю $$$10^9 + 7$$$.
Каждый тест содержит несколько наборов входных данных. Первая строка входных данных содержит одно целое число $$$t$$$ — количество наборов входных данных ($$$1 \leq t \leq 2 \cdot 10^5$$$). Далее следует описание наборов входных данных.
В первой описания набора входных данных дано целое число $$$n$$$ — количество навыков в игре ($$$2 \le n \le 2 \cdot 10^5$$$).
Во второй строке перечислены $$$n$$$ целых чисел $$$c_i$$$ — типы навыков ($$$1 \le c_i \le 10^9$$$).
В $$$i$$$-й из следующих $$$n - 1$$$ строк даны два целых числа $$$u_i$$$ и $$$v_i$$$ — номера навыков, один из которых напрямую зависит от другого ($$$1 \le u_i, v_i \le n$$$). Какой навык от какого зависит, определяется тем, какой навык выбран «корневым». Гарантируется, что структура зависимостей образует дерево.
В следующей строке дано целое число $$$q$$$ — количество запросов на переподвешивание дерева навыков $$$(1 \le q \le n$$$).
Последняя строка ввода содержит $$$q$$$ целых чисел $$$x_i$$$ — номера вершин, за которые переподвешивается дерево ($$$1 \le x_i \le n$$$).
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.
Для каждого запроса выведите в отдельной строке число пар похожих навыков по модулю $$$10^9 + 7$$$.
Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.
| Подзадача | Баллы | Доп. ограничения | Необходимые подзадачи | Информация о проверке |
| 0 | – | примеры из условия | полная | |
| 1 | 10 | $$$t \le 10$$$, $$$n \le 50$$$ | 0 | первая ошибка |
| 2 | 12 | $$$t \le 10$$$, $$$n \le 500$$$ | 0, 1 | первая ошибка |
| 3 | 12 | $$$c_i \le 3$$$ для всех $$$i$$$ | первая ошибка | |
| 4 | 17 | $$$c_i \le 20$$$ для всех $$$i$$$ | 0, 3 | первая ошибка |
| 5 | 25 | $$$q = 1$$$ | первая ошибка | |
| 6 | 24 | нет | 0 – 5 | первая ошибка |
1 7 1 1 2 4 3 3 4 1 2 1 3 2 4 4 5 3 6 3 7 7 1 2 3 4 5 6 7
1 1 1 1 0 0 1
1 7 1 2 2 3 3 3 3 1 2 1 3 2 4 4 5 3 6 3 7 7 1 2 3 4 5 6 7
4 3 3 3 1 1 1
| Name |
|---|