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
95
96
97
#include<bits/stdc++.h>
using namespace std;
using LL=long long;
#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<<$<<"; "),...)<<'\n';}(x)
#else
#define debug(...) {}
#endif

/*
 * Opis: Wyznacznik macierzy (modulo lub double)
 * Czas: O(n^3)
 * Użycie: determinant(a)
 */

constexpr int mod = int(1e9) + 7;
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() {
	cin.tie(0)->sync_with_stdio(0);
	int n;
	cin >> n;
	vector t(n, 0);
	REP (i, n)
		cin >> t[i];
	vector mat(n, vector (n, 0));
	REP (i, n)
		REP (j, i) {
			int g = __gcd(t[i], t[j]);
			mat[i][j] = mat[j][i] = -g;
			mat[i][i] += g;
			mat[j][j] += g;
		}
	debug(mat);
	REP (i, n)
		mat[i].pop_back();
	mat.pop_back();
	debug(mat);

	cout << determinant(mat) << endl;
}