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
#include <bits/stdc++.h>
typedef long long ll;
#define endl '\n'
//#define int ll
using namespace std;
const int N=5010;
const ll mod=1000'000'007;

ll binpow(ll a,ll b){
    if (!b) return 1ll;
    if (b%2) return binpow(a,b-1)*a%mod;
    else return binpow(a*a%mod,b/2ll);
}

int dsu[N];
int get(int x){
    if (x==dsu[x]) return x;
    return dsu[x]=get(dsu[x]);
}
ll a[N][N];
ll Det(int n){
    ll ans=1ll;
    for (int i=1;i<=n;i++){
        if (a[i][i]==0){
            for (int j=i+1;j<=n;j++){
                if (a[j][i]){
                    for (int t=1;t<=n;t++){
                        swap(a[i][t],a[j][t]);
                    }
                    break;
                }
            }
            ans=mod-ans;
        }
        if (a[i][i]==0){
            ans=0;
            break;
        }
        ll inv=binpow(a[i][i],mod-2);
        ans*=a[i][i];
        ans%=mod;
        for (int j=1;j<=n;j++){
            a[i][j]*=inv;
            a[i][j]%=mod;
        }
        for (int j=i+1;j<=n;j++){
            ll c=a[j][i];
            for (int t=1;t<=n;t++){
                a[j][t]-=a[i][t]*c;
                a[j][t]%=mod;
                a[j][t]+=mod;
                a[j][t]%=mod;
            }
        }
    }
    for (int i=1;i<=n;i++){
        ans*=a[i][i];
        ans%=mod;
    }
    return ans;
}
ll x[N];
ll d[N];
void solve(){
    int n;cin>>n;
    for (int i=1;i<=n;i++) cin>>x[i];
    for (int i=1;i<=n;i++){
        for (int j=1;j<=n;j++){
            if (i!=j){

                a[i][j]=-__gcd(x[i],x[j]);
                a[i][i]-=a[i][j];
            }
        }
    }
    ll ans=Det(n-1);
    cout<<ans<<'\n';



}
int32_t main()
{

    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int tt=1;
    while (tt--){
        solve();
    }

    return 0;

}

/**
5
2 3 6 12 4
5345

175,4644,51940
**/