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

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template <class t, class u>
void chmax(t& first, u second) {
  if (first < second) first = second;
}
template <class t, class u>
void chmin(t& first, u second) {
  if (second < first) first = second;
}
template <class t>
using vc = vector<t>;
template <class t>
using vvc = vc<vc<t>>;
using pi = pair<int, int>;
using vi = vc<int>;
template <class t, class u>
ostream& operator<<(ostream& os, const pair<t, u>& p) {
  return os << "{" << p.first << "," << p.second << "}";
}
template <class t>
ostream& operator<<(ostream& os, const vc<t>& v) {
  os << "{";
  for (auto e : v) os << e << ",";
  return os << "}";
}
using uint = unsigned;
using ull = unsigned long long;
template <class t, size_t n>
ostream& operator<<(ostream& os, const array<t, n>& first) {
  return os << vc<t>(first.begin(), first.end());
}
template <int i, class T>
void print_tuple(ostream&, const T&) {}
template <int i, class T, class H, class... Args>
void print_tuple(ostream& os, const T& t) {
  if (i) os << ",";
  os << get<i>(t);
  print_tuple<i + 1, T, Args...>(os, t);
}
template <class... Args>
ostream& operator<<(ostream& os, const tuple<Args...>& t) {
  os << "{";
  print_tuple<0, tuple<Args...>, Args...>(os, t);
  return os << "}";
}
template <class t>
void print(t x, int suc = 1) {
  cout << x;
  if (suc == 1) cout << "\n";
  if (suc == 2) cout << " ";
}
ll read() {
  ll i;
  cin >> i;
  return i;
}
vi readvi(int n, int off = 0) {
  vi v(n);
  for (int i = int(0); i < int(n); i++) v[i] = read() + off;
  return v;
}
template <class T>
void print(const vector<T>& v, int suc = 1) {
  for (int i = int(0); i < int(v.size()); i++)
    print(v[i], i == int(v.size()) - 1 ? suc : 2);
}
string readString() {
  string s;
  cin >> s;
  return s;
}
template <class T>
T sq(const T& t) {
  return t * t;
}
void yes(bool ex = true) {
  cout << "Yes"
       << "\n";
  if (ex) exit(0);
}
void no(bool ex = true) {
  cout << "No"
       << "\n";
  if (ex) exit(0);
}
void possible(bool ex = true) {
  cout << "Possible"
       << "\n";
  if (ex) exit(0);
}
void impossible(bool ex = true) {
  cout << "Impossible"
       << "\n";
  if (ex) exit(0);
}
constexpr ll ten(int n) { return n == 0 ? 1 : ten(n - 1) * 10; }
const ll infLL = LLONG_MAX / 3;
const int inf = INT_MAX / 2 - 100;
int topbit(signed t) { return t == 0 ? -1 : 31 - __builtin_clz(t); }
int topbit(ll t) { return t == 0 ? -1 : 63 - __builtin_clzll(t); }
int botbit(signed first) { return first == 0 ? 32 : __builtin_ctz(first); }
int botbit(ll first) { return first == 0 ? 64 : __builtin_ctzll(first); }
int popcount(signed t) { return __builtin_popcount(t); }
int popcount(ll t) { return __builtin_popcountll(t); }
bool ispow2(int i) { return i && (i & -i) == i; }
int mask(int i) { return (int(1) << i) - 1; }
bool inc(int first, int second, int c) {
  return first <= second && second <= c;
}
template <class t>
void mkuni(vc<t>& v) {
  sort(v.begin(), v.end());
  v.erase(unique(v.begin(), v.end()), v.end());
}
ll rand_int(ll l, ll r) {
  static random_device rd;
  static mt19937_64 gen(rd());
  return uniform_int_distribution<ll>(l, r)(gen);
}
template <class t>
int lwb(const vc<t>& v, const t& first) {
  return lower_bound(v.begin(), v.end(), first) - v.begin();
}
using uint = unsigned;
using ull = unsigned long long;
struct modinfo {
  uint mod, root;
};
template <modinfo const& ref>
struct modular {
  static constexpr uint const& mod = ref.mod;
  static modular root() { return modular(ref.root); }
  uint v;
  modular(ll vv = 0) { s(vv % mod + mod); }
  modular& s(uint vv) {
    v = vv < mod ? vv : vv - mod;
    return *this;
  }
  modular operator-() const { return modular() - *this; }
  modular& operator+=(const modular& rhs) { return s(v + rhs.v); }
  modular& operator-=(const modular& rhs) { return s(v + mod - rhs.v); }
  modular& operator*=(const modular& rhs) {
    v = ull(v) * rhs.v % mod;
    return *this;
  }
  modular& operator/=(const modular& rhs) { return *this *= rhs.inv(); }
  modular operator+(const modular& rhs) const { return modular(*this) += rhs; }
  modular operator-(const modular& rhs) const { return modular(*this) -= rhs; }
  modular operator*(const modular& rhs) const { return modular(*this) *= rhs; }
  modular operator/(const modular& rhs) const { return modular(*this) /= rhs; }
  modular pow(int n) const {
    modular res(1), x(*this);
    while (n) {
      if (n & 1) res *= x;
      x *= x;
      n >>= 1;
    }
    return res;
  }
  modular inv() const { return pow(mod - 2); }
  friend modular operator+(int x, const modular& y) { return modular(x) + y; }
  friend modular operator-(int x, const modular& y) { return modular(x) - y; }
  friend modular operator*(int x, const modular& y) { return modular(x) * y; }
  friend modular operator/(int x, const modular& y) { return modular(x) / y; }
  friend ostream& operator<<(ostream& os, const modular& m) {
    return os << m.v;
  }
  friend istream& operator>>(istream& is, modular& m) {
    ll x;
    is >> x;
    m = modular(x);
    return is;
  }
  bool operator<(const modular& r) const { return v < r.v; }
  bool operator==(const modular& r) const { return v == r.v; }
  bool operator!=(const modular& r) const { return v != r.v; }
  explicit operator bool() const { return v; }
};
constexpr modinfo base{1000000007, 0};
using mint = modular<base>;
const int vmax = 10000010;
int pri[vmax];
void initprime() {
  for (int i = int(2); i < int(vmax); i++)
    if (!pri[i])
      for (int j = i; j < vmax; j += i) pri[j] = i;
}
template <class t>
struct BIT {
  vc<t> buf;
  int s;
  BIT(int n = 0) { init(n); }
  void init(int n) { buf.assign(s = n, 0); }
  void add(int i, t v) {
    for (; i < s; i += (i + 1) & (-i - 1)) buf[i] += v;
  }
  t get(int i) {
    t res = 0;
    for (; i >= 0; i -= (i + 1) & (-i - 1)) res += buf[i];
    return res;
  }
  t sum(int second, int e) { return get(e - 1) - get(second - 1); }
};
template <class E>
struct HLD {
  vvc<E> g;
  int n, rt, cnt;
  vi sub, in, out, par, head, dep;
  int dfs1(int v, int p, int d) {
    par[v] = p;
    dep[v] = d;
    g[v].erase(remove(g[v].begin(), g[v].end(), p), g[v].end());
    for (auto& e : g[v]) {
      sub[v] += dfs1(e, v, d + 1);
      if (sub[g[v][0]] < sub[e]) swap(g[v][0], e);
    }
    return sub[v];
  }
  void dfs2(int v, int h) {
    in[v] = cnt++;
    head[v] = h;
    for (int to : g[v]) dfs2(to, to == g[v][0] ? h : to);
    out[v] = cnt++;
  }
  HLD() {}
  HLD(const vvc<E>& gg, int rr)
      : g(gg),
        n(g.size()),
        rt(rr),
        cnt(0),
        sub(n, 1),
        in(n),
        out(n),
        par(n, -1),
        head(n),
        dep(n) {
    dfs1(rt, -1, 0);
    dfs2(rt, rt);
  }
  int lca(int first, int second) {
    while (head[first] != head[second]) {
      if (dep[head[first]] > dep[head[second]]) swap(first, second);
      second = par[head[second]];
    }
    if (dep[first] > dep[second]) swap(first, second);
    return first;
  }
  int len(int first, int second) {
    return dep[first] + dep[second] - dep[lca(first, second)] * 2;
  }
  bool asde(int first, int second) {
    return in[first] <= in[second] && out[second] <= out[first];
  }
  vi index;
  void init() { index.resize(n); }
  vc<pi> tree_compress(vi vs) {
    assert(index.size());
    auto comp = [&](int x, int y) { return in[x] < in[y]; };
    sort(vs.begin(), vs.end(), comp);
    vs.erase(unique(vs.begin(), vs.end()), vs.end());
    int k = vs.size();
    for (int i = int(0); i < int(k - 1); i++) {
      vs.push_back(lca(vs[i], vs[i + 1]));
    }
    sort(vs.begin(), vs.end(), comp);
    vs.erase(unique(vs.begin(), vs.end()), vs.end());
    k = vs.size();
    for (int i = int(0); i < int(k); i++) index[vs[i]] = i;
    vc<pi> es;
    for (int i = int(1); i < int(k); i++) {
      int p = lca(vs[i - 1], vs[i]);
      es.emplace_back(vs[i], p);
    }
    return es;
  }
  void slv() {
    vc<tuple<int, int, int>> qs;
    for (int i = int(0); i < int(n); i++) {
      int first = read();
      while (first > 1) {
        int f = pri[first], c = 0;
        while (pri[first] == f) {
          qs.emplace_back(f, c * 2, i);
          c++;
          first /= f;
        }
      }
    }
    int q;
    cin >> q;
    vc<tuple<int, int, int>> ps;
    for (int i = int(0); i < int(q); i++) {
      int first, second;
      cin >> first >> second;
      first--;
      second--;
      int x;
      cin >> x;
      ps.emplace_back(first, second, lca(first, second));
      while (x > 1) {
        int f = pri[x], c = 0;
        while (pri[x] == f) {
          c++;
          x /= f;
        }
        qs.emplace_back(f, c * 2 - 1, i);
      }
    }
    sort(qs.begin(), qs.end());
    vi raw(n);
    BIT<int> bit(n * 2);
    void(0);
    void(0);
    auto addval = [&](int i, int v) {
      raw[i] += v;
      bit.add(in[i], v);
      bit.add(out[i], -v);
    };
    vc<mint> ans(q, 1);
    int pre = -1;
    vi chd;
    for (auto dt : qs) {
      int f, lv, i;
      tie(f, lv, i) = dt;
      void(0);
      if (pre != f) {
        for (auto j : chd) {
          addval(j, -raw[j]);
        }
        chd.clear();
        pre = f;
      }
      if (lv % 2 == 0) {
        addval(i, 1);
        chd.push_back(i);
      } else {
        int first, second, c;
        tie(first, second, c) = ps[i];
        int num =
            bit.sum(in[c], out[first]) + bit.sum(in[c], out[second]) - raw[c];
        void(0);
        ans[i] *= mint(f).pow(num);
      }
    }
    for (auto v : ans) cout << v << "\n";
  }
};
signed main() {
  cin.tie(0);
  ios::sync_with_stdio(0);
  cout << fixed << setprecision(20);
  initprime();
  int n;
  cin >> n;
  vvc<int> t(n);
  for (int _ = int(0); _ < int(n - 1); _++) {
    int first, second;
    cin >> first >> second;
    first--;
    second--;
    t[first].push_back(second);
    t[second].push_back(first);
  }
  HLD<int> hld(t, 0);
  hld.slv();
}