E. Задача Принца
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Действующими лицами этой задачи будут герои какого-нибудь недавно вышедшего в прокат фильма. Кажется, в последнее время много мемов по «Мстители: Война бесконечности». Я не смотрел ни одной части, поэтому лишь смутно знаю героев. Впрочем, это не помешает мне использовать их в задаче. Пусть героями нашей задачи будут Танос и Доктор Стрендж. Итак, Танос и Доктор Стрендж занимаются своими супергеройскими и суперзлодейскими делами, как вдруг они наталкиваются на обычную задачу по спортивному программированию.

Есть дерево размера $$$n$$$.

В каждой вершине $$$v$$$ записано целое положительное число $$$a_{v}$$$.

Нужно ответить на $$$q$$$ запросов.

Запрос задаётся в виде $$$u$$$ $$$v$$$ $$$x$$$.

Нужно посчитать $$$\prod_{w \in P} gcd(x, a_{w}) \mod (10^{9} + 7)$$$, где $$$P$$$ — множество вершин, лежащих на пути из $$$u$$$ в $$$v$$$. Иными словами, вычислите произведение $$$gcd(x, a_{w})$$$ для всех вершин $$$w$$$ на пути от $$$u$$$ до $$$v$$$. Так как произведение может быть большим, выведите его по модулю $$$10^9+7$$$. Здесь $$$gcd(s, t)$$$ обозначает наибольший общий делитель $$$s$$$ и $$$t$$$.

Обратите внимание, что сами числа в вершинах не изменяются.

Думаю, вам интереснее было бы смотреть на супергеройские похождения Доктора Стренджа и Таноса, чем на то, как они решают задачку. Поэтому вам предлагается решить задачу вместо них.

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

В первой строке записано одно целое число $$$n$$$ — размер дерева ($$$1 \le n \le 10^{5}$$$).

В следующих $$$n-1$$$ строках описываются рёбра дерева по одному в строке. $$$i$$$-е ребро описывается двумя целыми числами $$$u_{i}$$$ и $$$v_{i}$$$ ($$$1 \le u_{i}, v_{i} \le n$$$), которые означают, что ребро соединяет вершины $$$u_{i}$$$ и $$$v_{i}$$$. Гарантируется, что данные ребра задают дерево.

В следующей строке записаны $$$n$$$ целых положительных чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_{v} \le 10^{7}$$$).

В следующей строке записано одно целое положительное число $$$q$$$ ($$$1 \le q \le 10^{5}$$$) — количество запросов.

Наконец, в $$$q$$$ строках описываются запросы, каждое описывается тремя целыми числами $$$u_{i}$$$, $$$v_{i}$$$ и $$$x_{i}$$$ ($$$1 \le u_{i}, v_{i} \le n$$$, $$$1 \le x_{i} \le 10^{7}$$$).

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

Выведите $$$q$$$ чисел в отдельных строках — ответы на запросы в том порядке, в котором они заданы во входных данных. Выведите каждый ответ по модулю $$$10^9+7 = 1000000007$$$.

Примеры
Входные данные
4
1 2
1 3
1 4
6 4 9 5
3
2 3 6
2 3 2
3 4 7
Выходные данные
36
4
1
Входные данные
6
1 2
2 3
2 4
1 5
5 6
100000 200000 500000 40000 800000 250000
3
3 5 10000000
6 2 3500000
4 1 64000
Выходные данные
196000
12250
999998215