#P986E. Prince's Problem

    ID: 3474 远端评测题 3000ms 512MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>brute forcedata structuresmathnumber theorytrees*2800

Prince's Problem

Description

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 nn vertices.

In each vertex vv there is positive integer ava_{v}.

You have to answer qq queries.

Each query has a from uu vv xx.

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

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.

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

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

In the next line there are nn integers a1,a2,,ana_1, a_2, \ldots, a_n (1av1071 \le a_{v} \le 10^{7}).

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

And in the next qq lines the queries are described. Each query is described with three integers uiu_{i}, viv_{i} and xix_{i} (1ui,vin1 \le u_{i}, v_{i} \le n, 1xi1071 \le x_{i} \le 10^{7}).

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

Input

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

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

In the next line there are nn integers a1,a2,,ana_1, a_2, \ldots, a_n (1av1071 \le a_{v} \le 10^{7}).

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

And in the next qq lines the queries are described. Each query is described with three integers uiu_{i}, viv_{i} and xix_{i} (1ui,vin1 \le u_{i}, v_{i} \le n, 1xi1071 \le x_{i} \le 10^{7}).

Output

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

Samples

样例输入 1

4
1 2
1 3
1 4
6 4 9 5
3
2 3 6
2 3 2
3 4 7

样例输出 1

36
4
1

样例输入 2

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

样例输出 2

196000
12250
999998215