#include <bits/stdc++.h>
using namespace std;
const int MAXN = (int)1e5 + 10;
const int MAXLOG = 18;
const int MAXVAL = (int)1e7 + 10;
const int MOD = (long long)1e9 + 7;
int val[MAXN];
vector<int> g[MAXN];
int timer = 0;
int tin[MAXN];
int tout[MAXN];
int binup[MAXLOG][MAXN];
int er[MAXVAL];
int in_tree[MAXN];
int pos_in_tree[MAXN];
struct Node {
  vector<int> ch;
  int s;
};
vector<pair<int, int>> factorize(int a) {
  vector<pair<int, int>> ans;
  while (a > 1) {
    int cval = er[a];
    int cnt = 0;
    while (a % cval == 0) {
      ++cnt;
      a /= cval;
    }
    ans.push_back({cval, cnt});
  }
  return ans;
}
struct SegmentTree {
  SegmentTree() {}
  SegmentTree(const vector<pair<int, int>>& vals, long long prime) {
    int mx = 0;
    for (pair<int, int> p : vals) {
      mx = max(mx, p.second);
    }
    vs.resize(vals.size());
    int vsz = vals.size();
    for (int i = 0; i < vsz; ++i) {
      vs[i] = vals[i].first;
    }
    sz = 1;
    while (sz < vsz) {
      sz <<= 1;
    }
    segs.resize(2 * sz, vector<long long>(mx));
    for (int i = 0; i < vsz; ++i) {
      int len = vals[i].second;
      int cur = 1;
      for (int j = 0; j < len; ++j) {
        cur *= prime;
        segs[i + sz][j] = cur;
      }
      for (int j = len; j < mx; ++j) {
        segs[i + sz][j] = cur;
      }
    }
    for (int i = vsz; i < sz; ++i) {
      for (int j = 0; j < mx; ++j) {
        segs[i + sz][j] = 1;
      }
    }
    for (int i = sz - 1; i > 0; --i) {
      for (int j = 0; j < mx; ++j) {
        segs[i][j] = (segs[i * 2][j] * segs[i * 2 + 1][j]) % MOD;
      }
    }
  }
  long long get(int v, int vl, int vr, int l, int r, int bound) {
    if (vl > r || l > vr) {
      return 1;
    }
    if (l <= vl && vr <= r) {
      int csz = segs[v].size() - 1;
      return segs[v][min(csz, bound)];
    }
    int vm = (vl + vr) / 2;
    return (get(v * 2, vl, vm, l, r, bound) *
            get(v * 2 + 1, vm + 1, vr, l, r, bound)) %
           MOD;
  }
  long long get(int l, int r, int bound) {
    int posl = lower_bound(vs.begin(), vs.end(), l) - vs.begin();
    int posr = upper_bound(vs.begin(), vs.end(), r) - vs.begin();
    --posr;
    if (posl > posr) {
      return 1;
    }
    return get(1, 0, sz - 1, posl, posr, bound - 1);
  }
  int sz;
  vector<int> vs;
  vector<vector<long long>> segs;
};
struct CascadeTree {
  CascadeTree() {}
  CascadeTree(const vector<int>& path, int number) {
    first = path[0];
    int path_sz = path.size();
    for (int i = 0; i < path_sz; ++i) {
      in_tree[path[i]] = number;
      pos_in_tree[path[i]] = i;
    }
    unordered_map<int, vector<pair<int, int>>> mp;
    for (int i = 0; i < path_sz; ++i) {
      vector<pair<int, int>> fact = factorize(val[path[i]]);
      for (pair<int, int> p : fact) {
        mp[p.first].push_back({i, p.second});
      }
    }
    for (pair<int, vector<pair<int, int>>> cp : mp) {
      tree_map[cp.first] = SegmentTree(cp.second, cp.first);
    }
  }
  long long get(int l, int r, int prime, int bound) {
    if (tree_map.find(prime) == tree_map.end()) {
      return 1;
    }
    return tree_map[prime].get(l, r, bound);
  }
  long long get(int l, int r, const vector<pair<int, int>>& factor) {
    long long ans = 1;
    for (pair<int, int> p : factor) {
      ans *= get(l, r, p.first, p.second);
      ans %= MOD;
    }
    return ans;
  }
  int first;
  unordered_map<int, SegmentTree> tree_map;
};
vector<CascadeTree> paths;
Node tree[MAXN];
void make_tree(int v, int p) {
  tree[v].ch.clear();
  binup[0][v] = p;
  tree[v].s = 1;
  tin[v] = timer++;
  for (int u : g[v]) {
    if (u == p) {
      continue;
    }
    make_tree(u, v);
    tree[v].ch.push_back(u);
    tree[v].s += tree[u].s;
  }
  tout[v] = timer++;
}
bool is_par(int a, int b) { return (tin[a] <= tin[b]) && (tout[a] >= tout[b]); }
pair<int, int> get_lca(int a, int b) {
  if (is_par(a, b)) {
    return {a, -1};
  }
  if (is_par(b, a)) {
    return {b, -1};
  }
  for (int i = MAXLOG - 1; i >= 0; --i) {
    if (!is_par(binup[i][a], b)) {
      a = binup[i][a];
    }
  }
  return {binup[0][a], a};
}
void add_path(const vector<int>& path) {
  int sz = paths.size();
  paths.push_back(CascadeTree(path, sz));
}
void make_hld(int v, vector<int>& path) {
  path.push_back(v);
  if (tree[v].ch.size() == 0) {
    add_path(path);
    return;
  }
  int mx = 0;
  int mxv = -1;
  for (int u : tree[v].ch) {
    if (tree[u].s > mx) {
      mx = tree[u].s;
      mxv = u;
    }
  }
  for (int u : tree[v].ch) {
    if (u == mxv) {
      make_hld(u, path);
    } else {
      vector<int> new_path;
      make_hld(u, new_path);
    }
  }
}
long long get_ans(int v, int par, const vector<pair<int, int>>& factor) {
  if (in_tree[v] == in_tree[par]) {
    return paths[in_tree[v]].get(pos_in_tree[par], pos_in_tree[v], factor);
  }
  int u = paths[in_tree[v]].first;
  long long cans =
      paths[in_tree[v]].get(pos_in_tree[u], pos_in_tree[v], factor);
  cans *= get_ans(binup[0][u], par, factor);
  return cans % MOD;
}
int main() {
  ios_base::sync_with_stdio(false);
  memset(er, -1, sizeof(er));
  for (long long i = 2; i < MAXVAL; ++i) {
    if (er[i] == -1) {
      er[i] = i;
      for (long long j = i * i; j < MAXVAL; j += i) {
        er[j] = i;
      }
    }
  }
  int n;
  cin >> n;
  for (int i = 0; i < n - 1; ++i) {
    int a, b;
    cin >> a >> b;
    --a, --b;
    g[a].push_back(b);
    g[b].push_back(a);
  }
  for (int i = 0; i < n; ++i) {
    cin >> val[i];
  }
  make_tree(0, 0);
  for (int i = 1; i < MAXLOG; ++i) {
    for (int j = 0; j < n; ++j) {
      binup[i][j] = binup[i - 1][binup[i - 1][j]];
    }
  }
  vector<int> path;
  make_hld(0, path);
  int q;
  cin >> q;
  for (int i = 0; i < q; ++i) {
    int u, v, x;
    cin >> u >> v >> x;
    --u, --v;
    vector<pair<int, int>> factor = factorize(x);
    pair<int, int> plca = get_lca(u, v);
    if (plca.second == -1) {
      if (plca.first == u) {
        cout << get_ans(v, u, factor) << "\n";
      } else {
        cout << get_ans(u, v, factor) << "\n";
      }
      continue;
    }
    cout << (get_ans(u, plca.second, factor) * get_ans(v, plca.first, factor)) %
                MOD
         << "\n";
  }
  return 0;
}

### Prompt

Please formulate a Cpp solution to the following 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 ∏_{w ∈ 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

In the first line of input there is one integer n (1 ≤ n ≤ 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 ≤ u_{i}, v_{i} ≤ 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, …, a_n (1 ≤ a_{v} ≤ 10^{7}).

In the next line there is one integer q (1 ≤ q ≤ 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 ≤ u_{i}, v_{i} ≤ n, 1 ≤ x_{i} ≤ 10^{7}).

Output

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.

Examples

Input

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


Output

36
4
1


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


Output

196000
12250
999998215

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
const int MAXN = (int)1e5 + 10;
const int MAXLOG = 18;
const int MAXVAL = (int)1e7 + 10;
const int MOD = (long long)1e9 + 7;
int val[MAXN];
vector<int> g[MAXN];
int timer = 0;
int tin[MAXN];
int tout[MAXN];
int binup[MAXLOG][MAXN];
int er[MAXVAL];
int in_tree[MAXN];
int pos_in_tree[MAXN];
struct Node {
  vector<int> ch;
  int s;
};
vector<pair<int, int>> factorize(int a) {
  vector<pair<int, int>> ans;
  while (a > 1) {
    int cval = er[a];
    int cnt = 0;
    while (a % cval == 0) {
      ++cnt;
      a /= cval;
    }
    ans.push_back({cval, cnt});
  }
  return ans;
}
struct SegmentTree {
  SegmentTree() {}
  SegmentTree(const vector<pair<int, int>>& vals, long long prime) {
    int mx = 0;
    for (pair<int, int> p : vals) {
      mx = max(mx, p.second);
    }
    vs.resize(vals.size());
    int vsz = vals.size();
    for (int i = 0; i < vsz; ++i) {
      vs[i] = vals[i].first;
    }
    sz = 1;
    while (sz < vsz) {
      sz <<= 1;
    }
    segs.resize(2 * sz, vector<long long>(mx));
    for (int i = 0; i < vsz; ++i) {
      int len = vals[i].second;
      int cur = 1;
      for (int j = 0; j < len; ++j) {
        cur *= prime;
        segs[i + sz][j] = cur;
      }
      for (int j = len; j < mx; ++j) {
        segs[i + sz][j] = cur;
      }
    }
    for (int i = vsz; i < sz; ++i) {
      for (int j = 0; j < mx; ++j) {
        segs[i + sz][j] = 1;
      }
    }
    for (int i = sz - 1; i > 0; --i) {
      for (int j = 0; j < mx; ++j) {
        segs[i][j] = (segs[i * 2][j] * segs[i * 2 + 1][j]) % MOD;
      }
    }
  }
  long long get(int v, int vl, int vr, int l, int r, int bound) {
    if (vl > r || l > vr) {
      return 1;
    }
    if (l <= vl && vr <= r) {
      int csz = segs[v].size() - 1;
      return segs[v][min(csz, bound)];
    }
    int vm = (vl + vr) / 2;
    return (get(v * 2, vl, vm, l, r, bound) *
            get(v * 2 + 1, vm + 1, vr, l, r, bound)) %
           MOD;
  }
  long long get(int l, int r, int bound) {
    int posl = lower_bound(vs.begin(), vs.end(), l) - vs.begin();
    int posr = upper_bound(vs.begin(), vs.end(), r) - vs.begin();
    --posr;
    if (posl > posr) {
      return 1;
    }
    return get(1, 0, sz - 1, posl, posr, bound - 1);
  }
  int sz;
  vector<int> vs;
  vector<vector<long long>> segs;
};
struct CascadeTree {
  CascadeTree() {}
  CascadeTree(const vector<int>& path, int number) {
    first = path[0];
    int path_sz = path.size();
    for (int i = 0; i < path_sz; ++i) {
      in_tree[path[i]] = number;
      pos_in_tree[path[i]] = i;
    }
    unordered_map<int, vector<pair<int, int>>> mp;
    for (int i = 0; i < path_sz; ++i) {
      vector<pair<int, int>> fact = factorize(val[path[i]]);
      for (pair<int, int> p : fact) {
        mp[p.first].push_back({i, p.second});
      }
    }
    for (pair<int, vector<pair<int, int>>> cp : mp) {
      tree_map[cp.first] = SegmentTree(cp.second, cp.first);
    }
  }
  long long get(int l, int r, int prime, int bound) {
    if (tree_map.find(prime) == tree_map.end()) {
      return 1;
    }
    return tree_map[prime].get(l, r, bound);
  }
  long long get(int l, int r, const vector<pair<int, int>>& factor) {
    long long ans = 1;
    for (pair<int, int> p : factor) {
      ans *= get(l, r, p.first, p.second);
      ans %= MOD;
    }
    return ans;
  }
  int first;
  unordered_map<int, SegmentTree> tree_map;
};
vector<CascadeTree> paths;
Node tree[MAXN];
void make_tree(int v, int p) {
  tree[v].ch.clear();
  binup[0][v] = p;
  tree[v].s = 1;
  tin[v] = timer++;
  for (int u : g[v]) {
    if (u == p) {
      continue;
    }
    make_tree(u, v);
    tree[v].ch.push_back(u);
    tree[v].s += tree[u].s;
  }
  tout[v] = timer++;
}
bool is_par(int a, int b) { return (tin[a] <= tin[b]) && (tout[a] >= tout[b]); }
pair<int, int> get_lca(int a, int b) {
  if (is_par(a, b)) {
    return {a, -1};
  }
  if (is_par(b, a)) {
    return {b, -1};
  }
  for (int i = MAXLOG - 1; i >= 0; --i) {
    if (!is_par(binup[i][a], b)) {
      a = binup[i][a];
    }
  }
  return {binup[0][a], a};
}
void add_path(const vector<int>& path) {
  int sz = paths.size();
  paths.push_back(CascadeTree(path, sz));
}
void make_hld(int v, vector<int>& path) {
  path.push_back(v);
  if (tree[v].ch.size() == 0) {
    add_path(path);
    return;
  }
  int mx = 0;
  int mxv = -1;
  for (int u : tree[v].ch) {
    if (tree[u].s > mx) {
      mx = tree[u].s;
      mxv = u;
    }
  }
  for (int u : tree[v].ch) {
    if (u == mxv) {
      make_hld(u, path);
    } else {
      vector<int> new_path;
      make_hld(u, new_path);
    }
  }
}
long long get_ans(int v, int par, const vector<pair<int, int>>& factor) {
  if (in_tree[v] == in_tree[par]) {
    return paths[in_tree[v]].get(pos_in_tree[par], pos_in_tree[v], factor);
  }
  int u = paths[in_tree[v]].first;
  long long cans =
      paths[in_tree[v]].get(pos_in_tree[u], pos_in_tree[v], factor);
  cans *= get_ans(binup[0][u], par, factor);
  return cans % MOD;
}
int main() {
  ios_base::sync_with_stdio(false);
  memset(er, -1, sizeof(er));
  for (long long i = 2; i < MAXVAL; ++i) {
    if (er[i] == -1) {
      er[i] = i;
      for (long long j = i * i; j < MAXVAL; j += i) {
        er[j] = i;
      }
    }
  }
  int n;
  cin >> n;
  for (int i = 0; i < n - 1; ++i) {
    int a, b;
    cin >> a >> b;
    --a, --b;
    g[a].push_back(b);
    g[b].push_back(a);
  }
  for (int i = 0; i < n; ++i) {
    cin >> val[i];
  }
  make_tree(0, 0);
  for (int i = 1; i < MAXLOG; ++i) {
    for (int j = 0; j < n; ++j) {
      binup[i][j] = binup[i - 1][binup[i - 1][j]];
    }
  }
  vector<int> path;
  make_hld(0, path);
  int q;
  cin >> q;
  for (int i = 0; i < q; ++i) {
    int u, v, x;
    cin >> u >> v >> x;
    --u, --v;
    vector<pair<int, int>> factor = factorize(x);
    pair<int, int> plca = get_lca(u, v);
    if (plca.second == -1) {
      if (plca.first == u) {
        cout << get_ans(v, u, factor) << "\n";
      } else {
        cout << get_ans(u, v, factor) << "\n";
      }
      continue;
    }
    cout << (get_ans(u, plca.second, factor) * get_ans(v, plca.first, factor)) %
                MOD
         << "\n";
  }
  return 0;
}

```