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
87
88
89
90
91
92
93
94
//Franciszek Witt
#include<bits/stdc++.h>
using namespace std;
#define FOR(i,l,r) for(int i=(l);i<=(r);++i)
#define REP(i,n) FOR(i,0,(n)-1)
#define ssize(x) int(x.size())
template<class A,class B>auto&operator<<(ostream&o,pair<A,B>p){return o<<'('<<p.first<<", "<<p.second<<')';}
template<class T>auto operator<<(ostream&o,T x)->decltype(x.end(),o){o<<'{';int i=0;for(auto e:x)o<<(", ")+2*!i++<<e;return o<<'}';}
#ifdef DEBUG
#define debug(x...) cerr<<"["#x"]: ",[](auto...$){((cerr<<$<<"; "),...);}(x),cerr<<'\n'
#else
#define debug(...) {}
#endif
typedef long long ll;
//https://github.com/tonowak/acmlib/blob/master/code/math/determinant/main.cpp
constexpr int mod = 1000000007;
bool equal(int a, int b) {
	return a == b;
}
int mul(int a, int b) {
	return int((a * ll(b)) % mod);
}
int add(int a, int b) {
	a += b;
	return a >= mod ? a - mod : a;
}
int powi(int a, int b) {
	if(b == 0)
		return 1;
	int x = powi(a, b / 2);
	x = mul(x, x);
	if(b % 2 == 1)
		x = mul(x, a);
	return x;
}
int inv(int x) {
	return powi(x, mod - 2);
}
int divide(int a, int b) {
	return mul(a, inv(b));
}
int sub(int a, int b) {
	return add(a, mod - b);
}
using T = int;


T determinant(vector<vector<T>>& a) {
	int n = ssize(a);
	T res = 1;
	REP(i, n) {
		int b = i;
		FOR(j, i + 1, n - 1)
			if(abs(a[j][i]) > abs(a[b][i]))
				b = j;
		if(i != b)
			swap(a[i], a[b]), res = sub(0, res);
		res = mul(res, a[i][i]);
		if (equal(res, 0))
			return 0;
		FOR(j, i + 1, n - 1) {
			T v = divide(a[j][i], a[i][i]);
			if (not equal(v, 0))
				FOR(k, i + 1, n - 1)
					a[j][k] = sub(a[j][k], mul(v, a[i][k]));
		}
	}
	return res;
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    vector<int> v(n);
    for(auto &i : v)
        cin >> i;
    vector vv(n, vector(n, 0));
    REP(i, n) {
        REP(j, i) {
            if(i == j)
                continue;
            vv[i][j] = mod - __gcd(v[i], v[j]);
            vv[j][i] = vv[i][j];
            vv[i][i] = add(vv[i][i], mod - vv[i][j]);
            vv[j][j] = add(vv[j][j], mod - vv[i][j]);
            
        }
    }
    vv.resize(n - 1);
    REP(i, n - 1)
        vv[i].resize(n - 1);
    cout << determinant(vv) << endl;
}