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
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
#include "bits/stdc++.h" // Tomasz Nowak
using namespace std;     // University of Warsaw
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 << $ << "; "), ...); }(x), cerr << '\n'
#else
#define debug(...) {}
#endif

#if 1
bool equal(int a, int b) {
	return a == b;
}
constexpr int mod = int(1e9) + 7;
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;
#else
constexpr double eps = 1e-9;
bool equal(double a, double b) {
	return abs(a - b) < eps;
}
#define OP(name, op) double name(double a, double b) { return a op b; }
OP(mul, *)
OP(add, +)
OP(divide, /)
OP(sub, -)
using T = double;
#endif

void gauss(vector<vector<T>> &a) {
	int n = ssize(a); // liczba wierszy
	int m = ssize(a[0]); // liczba zmiennych

	vector<int> where(m, -1); // w ktorym wierszu jest zdefiniowana i-ta zmienna
	for(int col = 0, row = 0; col < m and row < n; ++col) {
		int sel = row;
		for(int y = row; y < n; ++y)
			if(abs(a[y][col]) > abs(a[sel][col]))
				sel = y;
		if(equal(a[sel][col], 0))
			continue;
		for(int x = col; x < m; ++x)
			swap(a[sel][x], a[row][x]);
		// teraz sel jest nieaktualne
		where[col] = row;

		for(int y = 0; y < n; ++y)
			if(y != row) {
				T wspolczynnik = divide(a[y][col], a[row][col]);
				for(int x = col; x < m; ++x)
					a[y][x] = sub(a[y][x], mul(wspolczynnik, a[row][x]));
			}
		++row;
	}
}

T determinant(vector<vector<T>> &a) {
	int n = ssize(a);
	assert(n == ssize(a[0]));
	gauss(a);
	T ret = 1;
	REP(i, n)
		ret = mul(ret, a[i][i]);
	return ret;
}

int main() {
	cin.tie(0)->sync_with_stdio(0);

	int n;
	cin >> n;
	vector<int> a(n);
	for(int &ai : a)
		cin >> ai;
	debug(n, a);

	vector<vector<int>> matrix(n - 1, vector<int>(n - 1));
	REP(i, n)
		REP(j, i) {
			int edge_cnt = gcd(a[i], a[j]);
			matrix[j][j] += edge_cnt;
			if(i != n - 1) {
				matrix[i][i] += edge_cnt;
				matrix[i][j] -= edge_cnt;
				matrix[j][i] -= edge_cnt;
			}
		}
	debug(matrix);

	cout << determinant(matrix) << '\n';
}