Problem: Tired of boring dates, Leha and Noora decided to play a game.

Leha found a tree with n vertices numbered from 1 to n. We remind you that tree is an undirected graph without cycles. Each vertex v of a tree has a number av written on it. Quite by accident it turned out that all values written on vertices are distinct and are natural numbers between 1 and n.

The game goes in the following way. Noora chooses some vertex u of a tree uniformly at random and passes a move to Leha. Leha, in his turn, chooses (also uniformly at random) some vertex v from remaining vertices of a tree (v ≠ u). As you could guess there are n(n - 1) variants of choosing vertices by players. After that players calculate the value of a function f(u, v) = φ(au·av) · d(u, v) of the chosen vertices where φ(x) is Euler's totient function and d(x, y) is the shortest distance between vertices x and y in a tree.

Soon the game became boring for Noora, so Leha decided to defuse the situation and calculate expected value of function f over all variants of choosing vertices u and v, hoping of at least somehow surprise the girl.

Leha asks for your help in calculating this expected value. Let this value be representable in the form of an irreducible fraction <image>. To further surprise Noora, he wants to name her the value <image>. 

Help Leha!

Input

The first line of input contains one integer number n (2 ≤ n ≤ 2·105) — number of vertices in a tree.

The second line contains n different numbers a1, a2, ..., an (1 ≤ ai ≤ n) separated by spaces, denoting the values written on a tree vertices.

Each of the next n - 1 lines contains two integer numbers x and y (1 ≤ x, y ≤ n), describing the next edge of a tree. It is guaranteed that this set of edges describes a tree.

Output

In a single line print a number equal to P·Q - 1 modulo 109 + 7.

Examples

Input

3
1 2 3
1 2
2 3


Output

333333338


Input

5
5 4 3 1 2
3 5
1 2
4 3
2 5


Output

8

Note

Euler's totient function φ(n) is the number of such i that 1 ≤ i ≤ n,and gcd(i, n) = 1, where gcd(x, y) is the greatest common divisor of numbers x and y.

There are 6 variants of choosing vertices by Leha and Noora in the first testcase:

  * u = 1, v = 2, f(1, 2) = φ(a1·a2)·d(1, 2) = φ(1·2)·1 = φ(2) = 1
  * u = 2, v = 1, f(2, 1) = f(1, 2) = 1
  * u = 1, v = 3, f(1, 3) = φ(a1·a3)·d(1, 3) = φ(1·3)·2 = 2φ(3) = 4
  * u = 3, v = 1, f(3, 1) = f(1, 3) = 4
  * u = 2, v = 3, f(2, 3) = φ(a2·a3)·d(2, 3) = φ(2·3)·1 = φ(6) = 2
  * u = 3, v = 2, f(3, 2) = f(2, 3) = 2



Expected value equals to <image>. The value Leha wants to name Noora is 7·3 - 1 = 7·333333336 = 333333338 <image>.

In the second testcase expected value equals to <image>, so Leha will have to surprise Hoora by number 8·1 - 1 = 8 <image>.

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1000000007;
template <typename T>
struct modular {
  constexpr modular() : val(0) {}
  constexpr modular(const modular<T>& _m) : val(_m.val) {}
  template <typename U>
  constexpr modular(const U& _r = U()) {
    val = -MOD <= _r && _r < MOD ? _r : _r % MOD;
    if (val < 0) {
      val += MOD;
    }
  }
  const T operator()() { return val; }
  template <typename U>
  explicit operator U() const {
    return static_cast<U>(val);
  }
  modular<T>& operator+=(const modular<T>& _m) {
    if ((val += _m.val) >= MOD) {
      val -= MOD;
    }
    return *this;
  }
  modular<T>& operator-=(const modular<T>& _m) {
    if ((val -= _m.val) < 0) {
      val += MOD;
    }
    return *this;
  }
  modular<T>& operator*=(const modular<T>& _m) {
    val = modular<T>(static_cast<int64_t>(val) * static_cast<int64_t>(_m.val))
              .val;
    return *this;
  }
  modular<T>& operator/=(const modular<T>& _m) {
    T a = _m.val, b = MOD, u = 0, v = 1;
    while (a != 0) {
      T q = b / a;
      b -= q * a;
      swap(a, b);
      u -= q * v;
      swap(u, v);
    }
    return *this *= u;
  }
  modular<T>& operator=(const modular<T>& _m) {
    val = _m.val;
    return *this;
  }
  template <typename U>
  modular<T>& operator+=(const U& _r) {
    return *this += modular<T>(_r);
  }
  template <typename U>
  modular<T>& operator-=(const U& _r) {
    return *this -= modular<T>(_r);
  }
  template <typename U>
  modular<T>& operator*=(const U& _r) {
    return *this *= modular<T>(_r);
  }
  template <typename U>
  modular<T>& operator/=(const U& _r) {
    return *this /= modular<T>(_r);
  }
  template <typename U>
  modular<T>& operator=(const U& _r) {
    val = modular<T>(_r).val;
    return *this;
  }
  modular<T> operator-() { return modular<T>(-val); }
  template <typename U>
  friend bool operator==(const modular<U>&, const modular<U>&);
  friend std::istream& operator>>(std::istream& os, modular<T>& _m) {
    os >> _m.val;
    _m *= 1;
    return os;
  }
  friend std::ostream& operator<<(std::ostream& os, const modular<T>& _m) {
    return os << _m.val;
  }
  template <typename U>
  modular<T> exp(U e) {
    modular<T> res = 1;
    modular<T> b = val;
    if (e < 0) {
      b = 1 / b;
      e *= -1;
    }
    for (; e; e >>= 1) {
      if (e & 1) {
        res *= b;
      }
      b *= b;
    }
    return res;
  }

 private:
  T val;
};
template <typename T>
inline modular<T> operator+(const modular<T>& _lhs, const modular<T>& _rhs) {
  return modular<T>(_lhs) += _rhs;
}
template <typename T, typename U>
inline modular<T> operator+(const modular<T>& _lhs, const U& _rhs) {
  return modular<T>(_lhs) += _rhs;
}
template <typename T, typename U>
inline modular<T> operator+(const U& _lhs, const modular<T>& _rhs) {
  return modular<T>(_lhs) += _rhs;
}
template <typename T>
inline modular<T> operator-(const modular<T>& _lhs, const modular<T>& _rhs) {
  return modular<T>(_lhs) -= _rhs;
}
template <typename T, typename U>
inline modular<T> operator-(const modular<T>& _lhs, const U& _rhs) {
  return modular<T>(_lhs) -= _rhs;
}
template <typename T, typename U>
inline modular<T> operator-(const U& _lhs, const modular<T>& _rhs) {
  return modular<T>(_lhs) -= _rhs;
}
template <typename T>
inline modular<T> operator*(const modular<T>& _lhs, const modular<T>& _rhs) {
  return modular<T>(_lhs) *= _rhs;
}
template <typename T, typename U>
inline modular<T> operator*(const modular<T>& _lhs, const U& _rhs) {
  return modular<T>(_lhs) *= _rhs;
}
template <typename T, typename U>
inline modular<T> operator*(const U& _lhs, const modular<T>& _rhs) {
  return modular<T>(_lhs) *= _rhs;
}
template <typename T>
inline modular<T> operator/(const modular<T>& _lhs, const modular<T>& _rhs) {
  return modular<T>(_lhs) /= _rhs;
}
template <typename T, typename U>
inline modular<T> operator/(const modular<T>& _lhs, const U& _rhs) {
  return modular<T>(_lhs) /= _rhs;
}
template <typename T, typename U>
inline modular<T> operator/(const U& _lhs, const modular<T>& _rhs) {
  return modular<T>(_lhs) /= _rhs;
}
template <typename T>
inline bool operator==(const modular<T>& _lhs, const modular<T>& _rhs) {
  return _lhs.val == _rhs.val;
}
template <typename T, typename U>
inline bool operator==(const modular<T>& _lhs, const U& _rhs) {
  return _lhs == modular<T>(_rhs);
}
template <typename T, typename U>
inline bool operator==(const U& _lhs, const modular<T>& _rhs) {
  return modular<T>(_lhs) == _rhs;
}
template <typename T>
inline bool operator!=(const modular<T>& _lhs, const modular<T>& _rhs) {
  return !(_lhs == _rhs);
}
template <typename T, typename U>
inline bool operator!=(const modular<T>& _lhs, const U& _rhs) {
  return !(_lhs == _rhs);
}
template <typename T, typename U>
inline bool operator!=(const U& _lhs, const modular<T>& _rhs) {
  return !(_lhs == _rhs);
}
struct Sieve {
  int sz;
  vector<bool> is;
  vector<int> prime;
  Sieve(int n = 45000) : sz(n) {
    prime.reserve(n / 6);
    is.assign(n + 1, true);
    is[0] = is[1] = false;
    for (int p = 2; (int64_t)p * p <= n; p++) {
      if (is[p]) {
        for (int i = p * p; i <= n; i += p) {
          is[i] = false;
        }
      }
    }
    for (int i = 2; i <= n; i++) {
      if (is[i]) prime.emplace_back(i);
    }
  }
  vector<pair<int, int>> factor(int x) {
    assert(x > 0 && (int64_t)sz * sz >= x);
    vector<pair<int, int>> res;
    for (const int& p : prime) {
      if ((int64_t)p * p > x) break;
      if (x % p == 0) {
        int e = 0;
        while (x % p == 0) {
          e++;
          x /= p;
        }
        res.emplace_back(p, e);
      }
    }
    if (x != 1) res.emplace_back(x, 1);
    return res;
  }
  vector<int> divs(int x, bool sorted = false) {
    vector<int> res;
    res.emplace_back(1);
    for (auto& p : factor(x)) {
      int b, e;
      tie(b, e) = p;
      int sz = res.size();
      int y = 1;
      while (e--) {
        y *= b;
        for (int i = 0; i < sz; i++) {
          res.emplace_back(res[i] * y);
        }
      }
    }
    if (sorted) sort(res.begin(), res.end());
    return res;
  }
  int num_divs(int x) {
    int res = 1;
    for (auto& pe : factor(x)) {
      res *= (1 + pe.second);
    }
    return res;
  }
  bool is_prime(int x) {
    if (x <= sz) return is[x];
    return factor(x)[0].first == x;
  }
  vector<int> p_divs(int x) {
    assert(x > 0 && (int64_t)sz * sz >= x);
    vector<int> res;
    for (const int& p : prime) {
      if ((int64_t)p * p > x) break;
      if (x % p == 0) {
        while (x % p == 0) {
          x /= p;
        }
        res.emplace_back(p);
      }
    }
    if (x != 1) res.emplace_back(x);
    return res;
  }
  int coprime(int m, int c) {
    int tmp = 0;
    auto di = p_divs(c);
    int sz = di.size();
    for (int msk = 1; msk < (1 << sz); msk++) {
      int prod = 1;
      for (int k = 0; k < sz; k++) {
        if (msk & (1 << k)) {
          prod *= di[k];
        }
      }
      int sign = (__builtin_popcount(msk) & 1) ? 1 : -1;
      tmp += sign * m / prod;
    }
    return m - tmp;
  };
  int phi(int x) {
    assert(x > 0);
    if (x == 1) return 1;
    int res = x;
    for (auto& p : p_divs(x)) {
      (res /= p) *= (p - 1);
    }
    return res;
  }
  vector<int> phi_table(int n) {
    assert(sz >= n);
    vector<int> res(n + 1);
    iota(res.begin(), res.end(), 0);
    for (const int& p : prime) {
      if (p > n) break;
      --res[p];
      for (int i = 2 * p; i <= n; i += p) (res[i] /= p) *= p - 1;
    }
    return res;
  }
  int8_t mu(int x) {
    assert(x > 0 && (int64_t)sz * sz >= x);
    if (x == 1) return 1;
    int cnt = 0;
    for (const int& p : prime) {
      if ((int64_t)p * p > x) break;
      if (x % p == 0) {
        cnt++;
        x /= p;
      }
      if (x % p == 0) {
        return 0;
      }
    }
    if (x != 1) cnt++;
    return (cnt & 1) ? -1 : 1;
  }
  vector<int8_t> mobius_table(int n) {
    assert(sz >= n);
    vector<int8_t> res(n + 1, 1);
    for (int i = 2; i <= n; i++) {
      if (is[i]) res[i] = -1;
      for (const int& p : prime) {
        if (p > i || (int64_t)p * i > n) break;
        if (i % p == 0) {
          res[i * p] = 0;
        } else {
          res[i * p] = -res[i];
        }
      }
    }
    return res;
  }
};
const int N = 2e5 + 10;
vector<int> divs[N];
vector<int> phi;
vector<int8_t> mu;
void prep() {
  Sieve s(N);
  phi = s.phi_table(N);
  mu = s.mobius_table(N);
  for (int i = 1; i < N; i++) {
    for (int j = i; j < N; j += i) {
      divs[j].push_back(i);
    }
  }
}
string to_string(string s) { return '"' + s + '"'; }
string to_string(bool x) { return (x ? "T" : "F"); }
string to_string(modular<int> x) { return to_string((int)x); }
string to_string(const char* s) { return to_string((string)s); }
template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
template <typename V>
string to_string(V v) {
  bool f = true;
  string res = "[";
  for (const auto& x : v) {
    if (!f) res += ", ";
    f = false;
    res += to_string(x);
  }
  res += "]";
  return res;
}
void debug() { cerr << endl; }
template <typename H, typename... T>
void debug(H h, T... t) {
  cerr << " " << to_string(h);
  debug(t...);
}
struct CentroidDecompositionAutomaton {
  int n;
  vector<vector<int>> g;
  vector<bool> trk;
  vector<int> sz;
  vector<int> centroids_tour;
  CentroidDecompositionAutomaton(int _n)
      : n(_n),
        g(n),
        trk(n, false),
        sz(n),
        a(n),
        F(n + 1),
        sum(n + 1),
        sum_d(n + 1) {
    input();
  }
  inline void add(int u, int v) {
    assert(0 <= u && u < n);
    assert(0 <= v && v < n);
    assert(u != v);
    g[u].emplace_back(v);
    g[v].emplace_back(u);
  }
  void input() {
    for (int i = 0; i < n; i++) {
      cin >> a[i];
    }
    int u, v;
    for (int _ = 1; _ < n; _++) {
      cin >> u >> v;
      u--;
      v--;
      add(u, v);
    }
  }
  int SZ, CEN;
  void find_centroid(int u, int p) {
    sz[u] = 1;
    bool yes = true;
    for (int v : g[u])
      if (!trk[v] && v != p) {
        find_centroid(v, u);
        yes &= sz[v] <= SZ / 2;
        sz[u] += sz[v];
      }
    yes &= SZ - sz[u] <= SZ / 2;
    if (yes) CEN = u;
  }
  void recalc_sz(int u, int p) {
    sz[u] = 1;
    for (int v : g[u])
      if (!trk[v] && v != p) {
        recalc_sz(v, u);
        sz[u] += sz[v];
      }
  }
  void get_centroids_tour(int u, int p) {
    find_centroid(u, -1);
    trk[u = CEN] = true;
    centroids_tour.push_back(u);
    recalc_sz(u, -1);
    for (int v : g[u])
      if (!trk[v] && v != p) {
        SZ = sz[v];
        get_centroids_tour(v, u);
      }
  }
  vector<int> a;
  vector<modular<int>> F, sum, sum_d;
  vector<int> history;
  void run() {
    centroids_tour.reserve(n);
    SZ = n;
    get_centroids_tour(0, -1);
    2019;
    fill(trk.begin(), trk.end(), false);
    for (int u : centroids_tour) {
      solve(u);
      trk[u] = true;
    }
  }
  void calc(int u, int p, modular<int> depth) {
    modular<int> x = phi[a[u]], y = phi[a[u]] * depth;
    for (int d : divs[a[u]]) {
      modular<int> X = sum[d], Y = sum_d[d];
      F[d] += x * Y + X * y;
    }
    for (int v : g[u])
      if (!trk[v] && v != p) {
        calc(v, u, depth + 1);
      }
  }
  void join(int u, int p, modular<int> depth) {
    modular<int> x = phi[a[u]], y = phi[a[u]] * depth;
    for (int d : divs[a[u]]) {
      sum[d] += x;
      sum_d[d] += y;
      history.push_back(d);
    }
    for (int v : g[u])
      if (!trk[v] && v != p) {
        join(v, u, depth + 1);
      }
  }
  void solve(int u) {
    for (int d : divs[a[u]]) {
      sum[d] += phi[a[u]];
      history.push_back(d);
    }
    for (int v : g[u])
      if (!trk[v]) {
        calc(v, u, 1);
        join(v, u, 1);
      }
    2019;
    while (!history.empty()) {
      int d = history.back();
      sum[d] = sum_d[d] = 0;
      history.pop_back();
    }
  }
};
template <typename T>
inline void zeta(vector<T>& f) {
  for (int n = f.size(), i = n - 1; i >= 1; i--)
    for (int j = i; (j += i) < n;) f[j] += f[i];
}
template <typename T>
inline void mobius(vector<T>& F) {
  for (int n = F.size(), i = 1; i < n; i++)
    for (int j = i; (j += i) < n;) F[j] -= F[i];
}
template <typename T>
inline void zeta_p(vector<T>& f) {
  for (int n = f.size(), i = 1; i < n; i++)
    for (int j = i; (j += i) < n;) f[i] += f[j];
}
template <typename T>
inline void mobius_p(vector<T>& F) {
  for (int n = F.size(), i = n - 1; i >= 1; i--)
    for (int j = i; (j += i) < n;) F[i] -= F[j];
}
void solve() {
  prep();
  int n;
  cin >> n;
  CentroidDecompositionAutomaton cda(n);
  cda.run();
  auto& F = cda.F;
  mobius_p(F);
  modular<int> res = 0;
  for (int i = 1; i <= n; i++) {
    res += i * F[i] / phi[i];
  }
  2019;
  2019;
  res /= n * modular<int>(n - 1) / 2;
  cout << res;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  solve();
  cout << endl;
}