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
#include<bits/stdc++.h>
using namespace std;
#ifdef LOC
template <class T, class U> auto &operator<<(ostream &out, pair<T, U> a) { return out << "(" << a.first << ", " << a.second << ")"; }
template <class T, class = class enable_if<!is_same<T, string>(), class T::iterator>::type> auto &operator<<(ostream &out, T a) {
    out << "{";
    bool fi = 1;
    for(auto b : a) {
        if(fi) {out<<b; fi=0;}
        else out<<", "<<b;
    }
    return out << "}";
}

template <class T, class X, class Y> auto &operator<<(ostream &out, const priority_queue<T,X,Y>& a) {auto b = a; vector<T> v; while(!b.empty()) {v.push_back(b.top()); b.pop();} return out<<v; }
void dump(){
   cerr << "\e[39m"<<"\n";
}
template <class T, class... Ts> void dump(T a, Ts... x) {
   cerr << a << ", ";
   dump(x...);
}
#define debug(...) cerr << "\e[91m"<<__func__<<":"<<__LINE__<<"\t"<<"[" #__VA_ARGS__ "]: ", dump(__VA_ARGS__)
#else
#define debug(...) ;
#endif

#define fwd(i, a, b) for(int i=(a);i<(int)(b);i++)
#define rep(i, n) for(int i=0;i<(int)(n);i++)
#define all(X) (X).begin(), (X).end()
#define sz(X) ((int)(X).size())
#define mp make_pair
#define st first
#define nd second
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;

template <int32_t _MODD>
    struct modint {
    int32_t value;
    modint() = default;
    modint(int32_t value_) : value(value_) {}
    inline modint<_MODD> operator + (modint<_MODD> other) const { int32_t c = this->value + other.value; return modint<_MODD>(c >= _MODD ? c - _MODD : c); }
    inline modint<_MODD> operator - (modint<_MODD> other) const { int32_t c = this->value - other.value; return modint<_MODD>(c <	0 ? c + _MODD : c); }
    inline modint<_MODD> operator * (modint<_MODD> other) const { int32_t c = (int64_t)this->value * other.value % _MODD; return modint<_MODD>(c < 0 ? c + _MODD : c); }
    inline modint<_MODD> & operator += (modint<_MODD> other) { this->value += other.value; if (this->value >= _MODD) this->value -= _MODD; return *this; }
    inline modint<_MODD> & operator -= (modint<_MODD> other) { this->value -= other.value; if (this->value <	0) this->value += _MODD; return *this; }
    inline modint<_MODD> & operator *= (modint<_MODD> other) { this->value = (int64_t)this->value * other.value % _MODD; if (this->value < 0) this->value += _MODD; return *this; }
    inline modint<_MODD> operator - () const { return modint<_MODD>(this->value ? _MODD - this->value : 0); }
    modint<_MODD> pow(uint64_t k) const {
        modint<_MODD> x = *this, y = 1;
        for (; k; k >>= 1) {
        if (k & 1) y *= x;
        x *= x;
        }
        return y;
    }
    modint<_MODD> inv() const { return pow(_MODD - 2); }  // _MODD must be a prime
    inline modint<_MODD> operator /  (modint<_MODD> other) const { return *this *  other.inv(); }
    inline modint<_MODD> operator /= (modint<_MODD> other)	   { return *this *= other.inv(); }
    inline bool operator == (modint<_MODD> other) const { return value == other.value; }
    inline bool operator != (modint<_MODD> other) const { return value != other.value; }
    inline bool operator < (modint<_MODD> other) const { return value < other.value; }
    inline bool operator > (modint<_MODD> other) const { return value > other.value; }
    };
    template <int32_t _MODD> modint<_MODD> operator * (int64_t value, modint<_MODD> n) { return modint<_MODD>(value) * n; }
    template <int32_t _MODD> modint<_MODD> operator * (int32_t value, modint<_MODD> n) { return modint<_MODD>(value % _MODD) * n; }
    template <int32_t _MODD> istream & operator >> (istream & in, modint<_MODD> &n) { return in >> n.value; }
    template <int32_t _MODD> ostream & operator << (ostream & out, modint<_MODD> n) { return out << n.value; }
typedef modint<(int)(1e9+7)> mint;



mint det(vector<vector<mint>>& a) {
    //https://github.com/kth-competitive-programming/kactl/blob/f6a97d9e5766c90ee71a97a90cd3faf6cff0ca72/content/numerical/IntDeterminant.h
    int n = sz(a); mint ans = 1;
    rep(i,n) {
        fwd(j,i+1,n) {
            while (a[j][i] != 0) {
                mint t = a[i][i] / a[j][i];
                if (t!=0) fwd(k,i,n)
                    a[i][k] = (a[i][k] - a[j][k] * t);
                swap(a[i], a[j]);
                ans *= -1;
            }
        }
        ans = ans * a[i][i];
        debug(a);
        if (ans==0) return 0;
    }
    return ans;
}

int32_t main(){
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    vi tab(n);
    rep(i,n)
        cin >> tab[i];
    
    vector<vector<mint> > M(n, vector<mint>(n));
    rep(i,n) rep(j,n) {
        if(j != i) {
            M[i][j] -= __gcd(tab[i],tab[j]);
            M[j][j] += __gcd(tab[i],tab[j]);
        }
    }
    M.pop_back();
    for(auto&a : M) a.resize(n-1);
    cout<<det(M)<<endl;

}