func_code_string: #include <bits/stdc++.h>   using namespace std;   const int N = 100005;   const int M = 10000005;   const int mo = 1000000007;   int pri[M / 10], mn[M], id[M];   vector<int> e[N];   int n, T, Q, dfn[N], ed[N];   int fa[N][20], dep[N];   int qx[N], qy[N], qL[N], qv[N];   int t[N * 2], vis[N], A[N], ans[N];   vector<int> vec[M / 10];   pair<int, int> q1[N], q2[N];   int power(int x, int y) {     int s = 1;     for (; y; y /= 2, x = 1ll * x * x % mo)       if (y & 1) s = 1ll * s * x % mo;     return s;   }   void change(int x, int v) {     for (; x <= 2 * n; x += x & (-x)) t[x] += v;   }   int ask(int x) {     int ans = 0;     for (; x; x -= x & (-x)) ans += t[x];     return ans;   }   void init() {     for (int i = (int)(2); i <= (int)(M - 1); i++) {       if (!mn[i]) mn[i] = i, pri[++*pri] = i;       for (int j = 1; j <= *pri && i * pri[j] < M; ++j) {         mn[i * pri[j]] = pri[j];         if (i % pri[j] == 0) break;       }     }     for (int i = (int)(1); i <= (int)(*pri); i++) id[pri[i]] = i;   }   void insert(int x, int id) {     for (; x != 1;) {       int v = mn[x];       for (; x % v == 0; x /= v)         ;       vec[::id[v]].push_back(id);     }   }   void dfs(int x) {     dfn[x] = ++*dfn;     for (auto i : e[x])       if (i != fa[x][0]) {         fa[i][0] = x;         dep[i] = dep[x] + 1;         dfs(i);       }     ed[x] = ++*dfn;   }   int LCA(int x, int y) {     if (dep[x] < dep[y]) swap(x, y);     int tmp = dep[x] - dep[y];     for (int i = (int)(0); i <= (int)(18); i++)       if (tmp & (1 << i)) x = fa[x][i];     for (int i = (int)(18); i >= (int)(0); i--)       if (fa[x][i] != fa[y][i]) x = fa[x][i], y = fa[y][i];     return x == y ? x : fa[x][0];   }   void solve(int id) {     int top1 = 0, top2 = 0;     for (auto i : vec[id])       if (i < 0)         q2[++top2] = pair<int, int>(-i, qv[-i]);       else         q1[++top1] = pair<int, int>(i, A[i]);     for (; top1 && top2;) {       int tmp1 = 0, tmp2 = 0;       for (int i = (int)(1); i <= (int)(top1); i++) {         change(dfn[q1[i].first], -1);         change(ed[q1[i].first], 1);       }       for (int i = (int)(1); i <= (int)(top2); i++) {         int at = q2[i].first;         int val1 = ask(ed[qL[at]] - 1) - ask(ed[qx[at]] - 1);         int val2 = ask(ed[qL[at]]) - ask(ed[qy[at]] - 1);         ans[at] = 1ll * ans[at] * power(pri[id], val1 + val2) % mo;       }       for (int i = (int)(1); i <= (int)(top1); i++) {         change(dfn[q1[i].first], 1);         change(ed[q1[i].first], -1);       }       for (int i = (int)(1); i <= (int)(top1); i++) q1[i].second /= pri[id];       for (int i = (int)(1); i <= (int)(top2); i++) q2[i].second /= pri[id];       for (int i = (int)(1); i <= (int)(top1); i++)         if (q1[i].second % pri[id] == 0) q1[++tmp1] = q1[i];       for (int i = (int)(1); i <= (int)(top2); i++)         if (q2[i].second % pri[id] == 0) q2[++tmp2] = q2[i];       top1 = tmp1;       top2 = tmp2;     }   }   int main() {     init();     scanf( %d , &n);     for (int i = (int)(1); i <= (int)(n - 1); i++) {       int x, y;       scanf( %d%d , &x, &y);       e[x].push_back(y);       e[y].push_back(x);     }     dfs(1);     for (int i = (int)(1); i <= (int)(18); i++)       for (int j = (int)(1); j <= (int)(n); j++)         fa[j][i] = fa[fa[j][i - 1]][i - 1];     for (int i = (int)(1); i <= (int)(n); i++) {       scanf( %d , &A[i]);       insert(A[i], i);     }     scanf( %d , &Q);     for (int i = (int)(1); i <= (int)(Q); i++) {       scanf( %d%d%d , &qx[i], &qy[i], &qv[i]);       qL[i] = LCA(qx[i], qy[i]);       insert(qv[i], -i);       ans[i] = 1;     }     for (int i = (int)(1); i <= (int)(*pri); i++) solve(i);     for (int i = (int)(1); i <= (int)(Q); i++) printf( %d n , ans[i]);   }   