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
#include <cstdio>
#include <algorithm>

const int md = 1000000007;

inline int add(int a, int b) {
	return a + b < md ? a + b : a + b - md;
}
inline int sub(int a, int b) {
	return a - b < 0 ? a - b + md : a - b;
}
inline int mul(int a, int b) {
	return (long long)a * b % md;
}
int po(int a, int b) {
	int r = 1;
	while (b) {
		if (b & 1) r = mul(r, a);
		a = mul(a, a);
		b >>= 1;
	}
	return r;
}
inline int inv(int a) {
	return po(a, md - 2);
}

const int N = 5000;
int n, a[N][N], x[N];

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

int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; ++i) {
		scanf("%d", x + i);
		for (int j = 0; j < i; ++j) {
			int d = gcd(x[j], x[i]);
			a[i][j] = a[j][i] = sub(0, d);
			a[i][i] += d;
			a[j][j] += d;
		}
	}
	if (n == 1) printf("1\n");
	else {
		--n;
		int ans = 1;
		for (int i = 0; i < n; ++i) {
			int r;
			for (r = i; !a[r][r]; ++r);
			std::swap(a[r], a[i]);
			ans = mul(ans, a[i][i]);
			int k = inv(a[i][i]);
			for (int j = i; j < n; ++j) a[i][j] = mul(a[i][j], k);
			for (int j = i + 1; j < n; ++j) if (a[j][i]) {
				int t = a[j][i];
				for (int k = 0; k < n; ++k) a[j][k] = sub(a[j][k], mul(t, a[i][k]));
			}
		}
		printf("%d\n", ans);
	}
	return 0;
}