Kamil likes streaming the competitive programming videos. His MeTube channel has recently reached 100 million subscribers. In order to celebrate this, he posted a video with an interesting problem he couldn't solve yet. Can you help him?

You're given a tree — a connected undirected graph consisting of n vertices connected by n - 1 edges. The tree is rooted at vertex 1. A vertex u is called an ancestor of v if it lies on the shortest path between the root and v. In particular, a vertex is an ancestor of itself.

Each vertex v is assigned its beauty x_v — a non-negative integer not larger than 10^{12}. This allows us to define the beauty of a path. Let u be an ancestor of v. Then we define the beauty f(u, v) as the greatest common divisor of the beauties of all vertices on the shortest path between u and v. Formally, if u=t_1, t_2, t_3, ..., t_k=v are the vertices on the shortest path between u and v, then f(u, v) = \gcd(x_{t_1}, x_{t_2}, ..., x_{t_k}). Here, \gcd denotes the greatest common divisor of a set of numbers. In particular, f(u, u) = \gcd(x_u) = x_u.

Your task is to find the sum

$$$ ∑_{u is an ancestor of v} f(u, v). $$$

As the result might be too large, please output it modulo 10^9 + 7.

Note that for each y, \gcd(0, y) = \gcd(y, 0) = y. In particular, \gcd(0, 0) = 0.

Input

The first line contains a single integer n (2 ≤ n ≤ 100 000) — the number of vertices in the tree.

The following line contains n integers x_1, x_2, ..., x_n (0 ≤ x_i ≤ 10^{12}). The value x_v denotes the beauty of vertex v.

The following n - 1 lines describe the edges of the tree. Each of them contains two integers a, b (1 ≤ a, b ≤ n, a ≠ b) — the vertices connected by a single edge.

Output

Output the sum of the beauties on all paths (u, v) such that u is ancestor of v. This sum should be printed modulo 10^9 + 7.

Examples

Input


5
4 5 6 0 8
1 2
1 3
1 4
4 5


Output


42


Input


7
0 2 3 0 0 0 0
1 2
1 3
2 4
2 5
3 6
3 7


Output


30

Note

The following figure shows all 10 possible paths for which one endpoint is an ancestor of another endpoint. The sum of beauties of all these paths is equal to 42:

<image>
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using ll = long long int;
using vll = vector<ll>;
using vvll = vector<vll>;
using vvvll = vector<vvll>;
using vd = vector<double>;
using vvd = vector<vd>;
using vvvd = vector<vvd>;
using P = pair<int, int>;
using Pll = pair<ll, ll>;
using cdouble = complex<double>;
const double eps = 1e-7;
bool feq(double x, double y) { return abs(x - y) <= eps; }
bool inrange(ll x, ll t) { return x >= 0 && x < t; }
bool inrange(vll xs, ll t) {
  for (const auto &x : xs)
    if (!(x >= 0 && x < t)) return false;
  return true;
}
int ceillog2(ll x) { return int(ceil(log2(x))); }
int floorlog2(ll x) { return int(floor(log2(x))); }
template <class T>
T reversed(T container) {
  reverse(container.begin(), container.end());
  return container;
}
template <class T>
void printv(const vector<T> &v) {
  for (const T &x : v) cout << x << " ";
  cout << endl;
}
template <class T>
void printmx(const vector<vector<T>> &mx) {
  for (const vector<T> &v : mx) printv(v);
}
ll rndf(double x) { return (ll)(x + (x >= 0 ? 0.5 : -0.5)); }
ll floorsqrt(ll x) {
  ll m = (ll)sqrt((double)x);
  return m + (m * m <= x ? 0 : -1);
}
ll ceilsqrt(ll x) {
  ll m = (ll)sqrt((double)x);
  return m + (x <= m * m ? 0 : 1);
}
ll rnddiv(ll a, ll b) { return (a / b + (a % b * 2 >= b ? 1 : 0)); }
ll ceildiv(ll a, ll b) { return (a / b + (a % b == 0 ? 0 : 1)); }
ll gcd(ll m, ll n) {
  if (n == 0)
    return m;
  else
    return gcd(n, m % n);
}
ll lcm(ll m, ll n) { return m * n / gcd(m, n); }
struct tree_t {
  using nodeval_t = ll;
  using edgeval_t = int;
  int n;
  vector<P> edges;
  vector<nodeval_t> vals;
  vector<edgeval_t> costs;
};
template <class val_t, class tree_t>
int make_treap(const vector<val_t> &a, const tree_t &T, int l = 0, int r = -1,
               int p = -1) {
  if (r == -1) {
    r = a.size();
    T.n = a.size();
  }
  if (r - l == 0) return -1;
  int mid = (l + r) / 2;
  if (p != -1) T.edges.push_back({mid, p});
  make_treap(a, T, l, mid, mid);
  make_treap(a, T, mid + 1, r, mid);
  return mid;
}
class Tree {
  using nodeval_t = ll;
  using edgeval_t = int;

 private:
  struct node {
    vi childs;
    int parent = -1;
    int deg = -1;
    int eid = -1;
    int subtree_n = 1;
    nodeval_t val;
    edgeval_t cost;
  };
  struct edgeinfo_t {
    int eid;
    int to;
    edgeval_t cost;
  };
  int n;
  static const nodeval_t init_val = 0;
  static const edgeval_t init_cost = 1;
  void tree_construction(const vector<vector<edgeinfo_t>> &edges) {
    leaves = {};
    queue<int> que;
    que.push(root);
    while (que.size()) {
      int a = que.front();
      que.pop();
      deg_order.push_back(a);
      if (a == Tree::root) nodes[a].deg = 0;
      int leaf_flag = true;
      for (int i = 0; i < int(edges[a].size()); i++) {
        int b = edges[a][i].to;
        if (nodes[b].deg != -1) {
          nodes[a].parent = b;
          nodes[a].eid = edges[a][i].eid;
          nodes[a].cost = edges[a][i].cost;
          nodes[a].deg = nodes[b].deg + 1;
        } else {
          leaf_flag = false;
          nodes[a].childs.push_back(b);
          que.push(b);
        }
      }
      if (leaf_flag) leaves.push_back(a);
    }
    for (int i = int(n) - 1; i >= 0; i--) {
      int a = deg_order[i];
      for (int j = 0; j < int(nodes[a].childs.size()); j++) {
        int b = nodes[a].childs[j];
        nodes[a].subtree_n += nodes[b].subtree_n;
      }
    }
  }

 public:
  vector<node> nodes;
  vi deg_order;
  vi leaves;
  int root;

 public:
  Tree(const tree_t &T, int root) {
    this->n = T.n;
    this->root = root;
    nodes.resize(n);
    for (int i = 0; i < int(n); i++) {
      nodes[i].val = (int)(T.vals.size()) > i ? T.vals[i] : init_val;
      nodes[i].cost = init_cost;
    }
    vector<vector<edgeinfo_t>> edges(n);
    for (int i = 0; i < int(n - 1); i++) {
      edges[T.edges[i].first].push_back(
          {i, T.edges[i].second,
           ((int)(T.costs.size()) > i ? T.costs[i] : init_cost)});
      edges[T.edges[i].second].push_back(
          {i, T.edges[i].first,
           ((int)(T.costs.size()) > i ? T.costs[i] : init_cost)});
    }
    tree_construction(edges);
    return;
  }
  int solve_diameter() {
    vi d(n, -1);
    queue<int> que;
    d[deg_order[n - 1]] = 0;
    que.push(deg_order[n - 1]);
    while (que.size()) {
      int a = que.front();
      que.pop();
      int p = nodes[a].parent;
      if (d[p] == -1) {
        d[p] = d[a] + 1;
        que.push(nodes[a].parent);
      }
      for (const auto &b : nodes[a].childs) {
        if (d[b] == -1) {
          d[b] = d[a] + 1;
          que.push(b);
        }
      }
    }
    return *max_element(d.begin(), d.end());
  }
  pair<int, vi> solve_center_of_gravity() {
    pair<int, vi> ret = {INT_MAX, {}};
    vi record(n, 1);
    for (const auto &a : deg_order) {
      int x = n - 1, max_x = INT_MIN;
      for (const auto &b : nodes[a].childs) {
        max_x = max(max_x, record[b]);
        x -= record[b];
        record[a] += record[b];
      }
      max_x = max(max_x, x);
      if (max_x < ret.first)
        ret = {max_x, {a}};
      else if (max_x == ret.first)
        ret.second.push_back(a);
    }
    sort(ret.second.begin(), ret.second.end());
    return ret;
  }
  vi solve_node_inclusion_cnt_in_all_path(bool enable_single_node_path) {
    vi ret(n, 0);
    for (int i = 0; i < int(n); i++) {
      int a = i;
      for (const auto &b : nodes[a].childs) {
        ret[i] +=
            nodes[b].subtree_n * (nodes[a].subtree_n - nodes[b].subtree_n - 1);
      }
      ret[i] /= 2;
      ret[i] += (nodes[a].subtree_n - 1) * (n - nodes[a].subtree_n);
      ret[i] += n - 1;
      if (enable_single_node_path) ret[i]++;
    }
    return ret;
  }
  vi solve_edge_inclusion_cnt_in_all_path() {
    vi ret(n - 1, 0);
    for (int i = 0; i < int(n); i++) {
      int eid = nodes[i].eid;
      if (eid < 0) continue;
      ret[eid] = nodes[i].subtree_n * (n - nodes[i].subtree_n);
    }
    return ret;
  }
  struct record_t {
    vi p;
    vll x;
  };
  record_t upd(int x, int p, record_t parent_record) {
    record_t ret;
    for (int i = 0; i < int(parent_record.p.size()); i++) {
      ll y = gcd(parent_record.x[i], nodes[x].val);
      if (i > 0 && ret.x.back() == y) {
        ret.p.back() = parent_record.p[i];
      } else {
        ret.p.push_back(parent_record.p[i]);
        ret.x.push_back(y);
      }
    }
    ll y = nodes[x].val;
    if (ret.x.back() == y) {
      ret.p.back() = nodes[x].deg;
    } else {
      ret.p.push_back(nodes[x].deg);
      ret.x.push_back(y);
    }
    return ret;
  }
  ll solve() {
    const ll MOD = ll(1e9) + 7;
    vector<record_t> records(n);
    records[root].p = {0};
    records[root].x = {nodes[root].val};
    for (const auto &x : deg_order) {
      if (x != root)
        records[x] = upd(x, nodes[x].parent, records[nodes[x].parent]);
    }
    ll ans = 0;
    for (const auto &x : deg_order) {
      ll acc = 0;
      for (int i = 0; i < int(records[x].p.size()); i++) {
        if (i == 0) {
          acc += (records[x].x[i] % MOD) * (records[x].p[i] + 1) % MOD;
        } else {
          acc += (records[x].x[i] % MOD) *
                 (records[x].p[i] - records[x].p[i - 1]) % MOD;
        }
      }
      ans += acc;
    }
    return ans % MOD;
  }
};
int main() {
  tree_t T;
  cin >> T.n;
  T.vals.resize(T.n);
  for (int i = 0; i < int(T.n); i++) {
    cin >> T.vals[i];
  }
  for (int i = 0; i < int(T.n - 1); i++) {
    int s, t;
    cin >> s >> t;
    s--;
    t--;
    T.edges.push_back({s, t});
  }
  Tree *tree = new Tree(T, 0);
  cout << tree->solve() << endl;
}
