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
//GRT_2018
#include <bits/stdc++.h>
#define PB push_back
#define ST first
#define ND second
//mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

using namespace std;

using ll = long long;
using pi = pair<int,int>;
using vi = vector<int>;

const int nax = 5000 + 10, mod = 1e9 + 7;
int n;
int val[nax];
int m[nax][nax];

int fastpow(int a, int b) {
	int w = 1;
	while (b) {
		if (b & 1) w = ((ll)w * a) % mod;
		b >>= 1;
		a = ((ll)a * a) % mod;
	}
	return w;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	for (int i = 0; i < n; ++i) {
		cin >> val[i];
	}
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			if (i == j) {
				for (int k = 0; k < n; ++k) {
					if (k == i) continue;
					m[i][i] += gcd(val[i], val[k]);
				}
			} else {
				m[i][j] = -gcd(val[i], val[j]);
			}
		}
	}
	n--;
	int row = 0, col = 0;
	int par = 0;
	while (row < n && col < n) {
		int id = -1;
		for (int i = row; i < n; ++i) {
			if (m[i][col] != 0) {
				id = i;
			}
		}
		if (id == -1) {
			col++;
			continue;
		}
		if (row != id) {
			for (int i = col; i < n; ++i) {
				swap(m[row][i], m[id][i]);
			}
			par ^= 1;
		}
		int inv = fastpow(m[row][col], mod - 2);
		for (int i = row + 1; i < n; ++i) {
			if (m[i][col] == 0) continue;
			ll mul = ((ll)inv * m[i][col]) % mod;
			for (int j = col; j < n; ++j) {
				m[i][j] = (m[i][j] - (ll)mul * m[row][j]) % mod;
			}
		}
		row++;
	}
	ll det = 1;
	for (int i = 0; i < n; ++i) {
		det = (det * m[i][i]) % mod;
	}
	if (par & 1) det = -det;
	if (det < 0) det += mod;
	cout << det;
}