#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <queue>

#include <bitset>

#include <string>

#include <algorithm>

#include <iostream>

#include <map>

#define inf 0x3f3f3f3f

#define inf64 0x3f3f3f3f3f3f3f3f

using namespace std;

const int maxn = 1e5 + ;

const int mod = 1e9 + ;

typedef long long ll;

typedef pair<ll, ll> P;

vector<P>val[maxn];

vector<int>G[maxn];

ll a[maxn], ans;

void add(int u, int v) {

    G[u].push_back(v);

    G[v].push_back(u);

}

ll gcd(ll a, ll b) {

    return b ==  ? a : gcd(b, a%b);

}

void dfs(int u, int pre,int dep) {

    for (int i = ; i < G[u].size(); i++) {

        int v = G[u][i];

        if (v == pre) continue;

        for (int j = ; j < val[u].size(); j++) {

            P now = val[u][j];

            ll ans = gcd(now.first, a[v]);

            int len = val[v].size();

            if (len ==  || ans != val[v][len - ].first) val[v].push_back(make_pair(ans, now.second));

        }

        val[v].push_back(make_pair(a[v], dep + ));

        dfs(v, u, dep + );

    }

}

void dfs1(int u, int pre) {

    for (int i = ; i < val[u].size(); i++) {

        ans += (val[u][i].second - val[u][i - ].second) % mod*val[u][i - ].first%mod;

        ans %= mod;

    }

    ans += a[u] % mod;

    ans %= mod;

    for (int i = ; i < G[u].size(); i++) {

        int v = G[u][i];

        if (v == pre) continue;

        dfs1(v, u);

    }

}

/*

void dfsprint(int u, int pre) {

    for (int i = 0; i < val[u].size(); i++) {

        printf("ww u=%d %lld %lld\n", u, val[u][i].first, val[u][i].second);

    }

    for (int i = 0; i < G[u].size(); i++) {

        int v = G[u][i];

        if (v == pre) continue;

        dfsprint(v, u);

    }

}

*/

int main() {

    int n;

    scanf("%d", &n);

    for (int i = ; i <= n; i++) scanf("%lld", &a[i]);

    for (int i = ; i < n; i++) {

        int u, v;

        scanf("%d%d", &u, &v);

        add(u, v);

    }

    val[].push_back(make_pair(a[], ));

    dfs(, -, );

    ans = ;

    dfs1(, -);

//    dfsprint(1, -1);

    printf("%lld\n", ans);

    return ;

}