让这个问题的主角是最近某部电影中的人物。新复仇者联盟似乎引起了很大的轰动。我没有看过该系列的任何部分,也不太了解其中的英雄,但这不会阻止我在这个问题陈述中使用他们。因此,灭霸和奇异博士正在做他们的超级英雄和超级恶棍的事情,但突然他们偶然发现了一个常规的竞争性编程问题。
给你一棵有 $$$n$$$ 个顶点的树。
每个顶点 $$$v$$$ 都有一个正整数 $$$a_{v}$$$。
您必须回答 $$$q$$$ 查询。
每个查询都有一个 from $$$u$$$ $$$v$$$ $$$x$$$。
您必须计算 $$$\prod_{w \in P} gcd(x, a_{w}) \mod (10^{9} + 7)$$$,其中 $$$P$$$ 是从 $$$u$$$ 到 $$$v$$$ 的路径上的一组顶点。换句话说,您要计算从 $$$u$$$ 到 $$$v$$$ 路径上所有顶点 $$$w$$$ 的 $$$gcd(x, a_{w})$$$ 的乘积。由于它可能很大,请以 $$$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$$$。将每个数字打印在单独的行上。
示例
输入 #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