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
#include <bits/stdc++.h>

using namespace std;

using ll = long long int;
const ll MOD = 1000000007;

ll sqr(ll x) {
  return (x * x) % MOD;
}

ll pow(ll x, ll b) {
  if (b == 0) return 1;
  if (b % 2 == 0) return sqr(pow(x, b / 2));
  return (x * pow(x, b - 1)) % MOD;
}

ll inv(ll x) {
  return pow(x, MOD - 2);
}


const int MAXN = 5010;

int A[MAXN];
ll MAT[MAXN][MAXN];
int sign = 1;


int main() {
  int n;
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    scanf("%d", A + i);
  }

  for (int i = 1; i <= n; i++) {
    int sum = 0;
    for (int j = 1; j <= n; j++) {
      if (i != j) {
        int d = __gcd(A[i], A[j]);
        sum += d;
        MAT[i][j] = MOD - d;
      }
    }
    MAT[i][i] = sum;
  }

  for (int i = 1; i < n; i++) {
    if (MAT[i][i] == 0) {
      for (int j = i + 1; j < n; j++) {
        if (MAT[j][i] != 0) {
          for (int k = i; k < n; k++) {
            swap(MAT[i][k], MAT[j][k]);
          }
          break;
        }
      }
      sign *= -1;
    }

    for (int j = i + 1; j < n; j++) {
      ll xd = (MAT[j][i] * inv(MAT[i][i])) % MOD;
      for (int k = 1; k < n; k++) {
        MAT[j][k] -= xd * MAT[i][k];
        MAT[j][k] %= MOD;
        if (MAT[j][k] < 0) MAT[j][k] += MOD;
      }
    }
  }

  ll det = 1;
  for (int i = 1; i < n; i++) {
    det = (det * MAT[i][i]) % MOD;
  }
  if (sign == -1) {
    det = MOD - det;
    if (det == MOD) det = 0;
  }
  printf("%lld\n", det);
}