CF986E.Prince's Problem

Let the main characters of this problem be personages from some recent movie. New Avengers seem to make a lot of buzz. I didn't watch any part of the franchise and don't know its heroes well, but it won't stop me from using them in this problem statement. So, Thanos and Dr. Strange are doing their superhero and supervillain stuff, but then suddenly they stumble across a regular competitive programming problem.

You are given a tree with $n$ vertices.

In each vertex $v$ there is positive integer $a_{v}$.

You have to answer $q$ queries.

Each query has a from $u$ $v$ $x$.

You have to calculate $\prod_{w \in P} gcd(x, a_{w}) \mod (10^{9} + 7)$, where $P$ is a set of vertices on path from $u$ to $v$. In other words, you are to calculate the product of $gcd(x, a_{w})$ for all vertices $w$ on the path from $u$ to $v$. As it might be large, compute it modulo $10^9+7$. Here $gcd(s, t)$ denotes the greatest common divisor of $s$ and $t$.

Note that the numbers in vertices do not change after queries.

I suppose that you are more interested in superhero business of Thanos and Dr. Strange than in them solving the problem. So you are invited to solve this problem instead of them.

本题的主角来自某部近期上映的电影。新复仇者联盟似乎引起了广泛关注。我并未观看过该系列电影的任何一部，也不太了解其中的英雄人物，但这并不会妨碍我在本题题面中使用他们。于是，灭霸（Thanos）与奇异博士（Dr. Strange）正在各自履行超级英雄与超级反派的职责，却突然意外撞上了一道普通的算法竞赛题目。

给你一棵包含 $n$ 个顶点的树。

每个顶点 $v$ 上有一个正整数 $a_{v}$。

你需要回答 $q$ 个询问。

每个询问形如 $u$ $v$ $x$。

你需要计算 $\prod_{w \in P} \gcd(x, a_{w}) \bmod (10^{9} + 7)$，其中 $P$ 表示从顶点 $u$ 到顶点 $v$ 的路径上所有顶点构成的集合。换言之，你需要计算路径 $u \to v$ 上每个顶点 $w$ 对应的 $\gcd(x, a_{w})$ 的乘积，并对 $10^9+7$ 取模。此处 $\gcd(s, t)$ 表示 $s$ 与 $t$ 的最大公约数。

注意：顶点上的数值在所有询问过程中均不发生改变。

我们猜想，你可能更关心灭霸与奇异博士的超级英雄事务，而非他们解这道题的过程。因此，诚邀你代替他们来解决本题。

In the first line of input there is one integer $n$ ($1 \le n \le 10^{5}$) — the size of the tree.

In the next $n-1$ lines the edges of the tree are described. The $i$-th edge is described with two integers $u_{i}$ and $v_{i}$ ($1 \le u_{i}, v_{i} \le n$) and it connects the vertices $u_{i}$ and $v_{i}$. It is guaranteed that graph with these edges is a tree.

In the next line there are $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_{v} \le 10^{7}$).

In the next line there is one integer $q$ ($1 \le q \le 10^{5}$) — the number of queries.

And in the next $q$ lines the queries are described. Each query is described with three integers $u_{i}$, $v_{i}$ and $x_{i}$ ($1 \le u_{i}, v_{i} \le n$, $1 \le x_{i} \le 10^{7}$).

输入的第一行包含一个整数 $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}$）描述。

Print $q$ numbers — the answers to the queries in the order they are given in the input. Print each answer modulo $10^9+7 = 1000000007$. Print each number on a separate line.

输出 $q$ 个数字——即按输入中给出的顺序对应的查询答案。每个答案需对 $10^9+7 = 1000000007$ 取模。每个数字单独占一行。