1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include <iostream>
#include <vector>
#include <functional>
using namespace std;
const int MOD = 1000000007;

int gcd(int a, int b) {
    while (a && b)
        if (a < b)
            b %= a;
        else
            a %= b;
    return a + b;
}

struct Edge {
    int a, b, val;
};

struct UnionFind {
    vector<int>parent;

    UnionFind(int n) {
        parent.resize(n);
        for (int i = 0; i < n; i++)
            parent[i] = i;
    }

    int find(int x) {
        if (parent[x] == x)
            return x;
        return parent[x] = find(parent[x]);
    }

    void merge(int x, int y) {
        x = find(x);
        y = find(y);
            parent[x] = y;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    vector<int>A(n);
    for (int& x : A)
        cin >> x;

    vector<Edge>E;
    for (int i = 1; i < n; i++)
        for (int j = 0; j < i; j++)
            E.push_back(Edge{i, j, gcd(A[i], A[j])});

    long long result = 0;
    UnionFind UF(n);

    function<void(int,int,UnionFind&, long long)> R = [&](int estart, int eleft, UnionFind& uf, long long acc) {
        int first = -1;
        for (int eid = estart; eid < (int)E.size() - eleft + 1; eid++)
            if (uf.find(E[eid].a) != uf.find(E[eid].b)) {
                if (eleft == 1)
                    result = (result + acc * E[eid].val) % MOD;
                else if (first == -1) {
                    first = eid;
                }
                else {
                    UnionFind new_uf(uf);
                    new_uf.merge(E[eid].a, E[eid].b);
                    R(eid + 1, eleft - 1, new_uf, (acc * E[eid].val) % MOD);
                }
            }
        if (first != -1) {
            uf.merge(E[first].a, E[first].b);
            R(first + 1, eleft - 1, uf, (acc * E[first].val) % MOD);
        }
    };

    R(0, n - 1, UF, 1);
    cout << result << endl;

    return 0;
}