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
#include <bits/stdc++.h>
#define maxn 5005
#define mod 1000000007ll
#define ll long long
using namespace std;

ll odw(ll a)
{
	ll ret = 1ll;
	for(ll b = mod-2ll; b; b >>= 1)
	{
		if(b&1ll) ret = (ret*a)%mod;
		a = (a*a)%mod;
	}
	return ret;
}

int wej[maxn];
ll laplas[maxn][maxn];

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	int n;
	cin >> n;
	for(int i = 1; i <= n; ++i) cin >> wej[i];
	
	for(int i = 1; i <= n; ++i) for(int j = 1; j <= n; ++j) if(i != j)
	{
		laplas[i][j] = -__gcd(wej[i], wej[j]);
		laplas[i][i] += __gcd(wej[i], wej[j]);
	}
	--n;
	
	// bazowane na https://en.wikipedia.org/wiki/LU_decomposition#Code_examples
	for(int i = n; i; --i) for(int j = i; --j;)
	{
		laplas[j][i] = (laplas[j][i]*odw(laplas[i][i]))%mod;
		for(int k = i; --k;) laplas[j][k] = (laplas[j][k]-laplas[j][i]*laplas[i][k])%mod;
	}
	// koniec
	
	ll wyn = 1ll;
	for(int i = 1; i <= n; ++i) wyn = (wyn*laplas[i][i])%mod;
	if(wyn < 0ll) wyn += mod;
	cout << wyn;
	return 0;
}