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
import numpy as np


def gcd(a, b):
    while b != 0:
        r = a % b
        a = b
        b = r
    return a


class Solver:
    def __init__(self):
        self.n = 0
        self.v = []
        self.d = []
        self.ec = None

    def read_data(self):
        self.n = int(input().strip())
        v = [0] * self.n
        d = [0] * self.n
        inp = input().strip().split(' ')
        for i in range(self.n):
            v[i] = int(inp[i])
        self.v = v
        self.d = d
        # ec = np.eye(self.n)
        ec = np.full(shape=[self.n, self.n], fill_value=0, dtype=int)
        for i in range(self.n):
            ec[i][i] = 0  # no loops
            for j in range(i+1, self.n):
                ec[i][j] = gcd(v[i], v[j])
                ec[j][i] = ec[i][j]
                d[i] += ec[i][j]
                d[j] += ec[i][j]
        self.ec = ec

    def solve(self):
        n = self.n
        d = self.d
        ec = self.ec
        # a = np.eye(self.n-1)
        a = np.full(shape=[n-1,n-1], fill_value=0, dtype=int)
        for i in range(n - 1):
            for j in range(n - 1):
                if i == j:
                    a[i][j] = d[i]
                else:
                    a[i][j] = -ec[i][j]
        # print(a)
        print(round(np.linalg.det(a)) % 1000000007)


s = Solver()
s.read_data()
s.solve()