Prince's Problem
Contest: Codeforces Round 485 (Div. 1)
Difficulty rating: 2800
Tags: brute force, data structures, math, number theory, trees

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.

Input format:
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}$$$).

Output format:
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.

Constraints:
Time limit: 3.0 s
Memory limit: 512.0 MB

Example input:
4
1 2
1 3
1 4
6 4 9 5
3
2 3 6
2 3 2
3 4 7

Example output:
36
4
1

Example input:
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

Example output:
196000
12250
999998215

Editorial:
Let's solve the problem offline and independently for all primes, then multiply the answers. The sum of powers of all primes is $$$O((n+q) \log C)$$$. To factorize numbers we will precalculate smallest prime divisor for all numbers using sieve.
For fixed prime $$$p$$$ let's write its power $$$b_v$$$ in every vertex. Then if $$$p$$$ is in $$$x$$$ from query in power $$$z$$$, then the query become "calculate $$$\sum_{v} min(b_v, z)$$$". Let's do the following. We will start with $$$c_v = 0$$$ in all vertices. Then we will iterate over $$$w$$$ — the power of $$$p$$$ — from $$$1$$$ to maximal power in queries. If $$$b_v \ge w$$$, then increase $$$c_v$$$ by $$$1$$$. Now in all vertices $$$c_v = min(b_v, w)$$$ so to answer all queries with $$$z=w$$$ we should just take sum on path. This can be done if we will maintain $$$c_v$$$ in Fenwick tree over Euler tour of our tree (this allows to calculate sum on path to root in $$$O(\log n)$$$ time, to get sum on arbitrary path we also need to compute LCA).
The number of queries to Fenwick tree is $$$O((n+q) \log C)$$$, so total complexity is $$$O((n+q) \log C \log n)$$$.