#include<bits/stdc++.h>
using namespace std;
const int N=26;
const int mod=1e9+7;
int n,a[N],dp[(1<<N)];
vector<int>val,pos[N];
int calc(int mask)
{
int &res=dp[mask];
if(res!=-1) return res;
res=0;
int first_bit=-1;
int second_bit=-1;
for(int i=0;i<n;i++)
{
if(mask>>i&1)
{
if(first_bit==-1) first_bit=i;
else if(second_bit==-1) second_bit=i;
}
}
if(first_bit==n-1&&second_bit==-1) return res=1;
else if(first_bit==second_bit-1) res=calc(mask-(1<<first_bit));/// ko xây thêm cây dưới đỉnh first_bit
for(int ii=0;ii<val.size();ii++)
{
for(int jj=ii;jj<val.size();jj++)
{
int x=val[ii];
int y=val[jj];
if(__gcd(x,y)!=val[a[first_bit]]) continue;
int mul=1;
if(pos[ii].empty()) continue;
mul=mul*pos[ii].size();
int i=pos[ii].back();
pos[ii].pop_back();
if(pos[jj].empty())
{
pos[ii].push_back(i);
continue ;
}
mul=mul*pos[jj].size();
int j=pos[jj].back();
pos[jj].pop_back();
if(x==y) mul=(1ll*mul*(mod+1)/2)%mod;
if(first_bit!=second_bit-1&&i!=first_bit+1) mul=0;/// nếu first_bit và second_bit ko liền nhau bắt buộc i phải bằng first_bit+1.
int cur_mask=mask-(1<<first_bit);/// xóa first_bit
cur_mask+=(1<<i)+(1<<j);/// them đỉnh i và j.
res=(res+1ll*calc(cur_mask)*mul%mod)%mod;
pos[jj].push_back(j);
pos[ii].push_back(i);
}
}
return res;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
memset(dp,-1,sizeof dp);
cin>>n;
for(int i=0;i<n;i++)
{
cin>>a[i];
val.push_back(a[i]);
}
sort(val.begin(),val.end());
val.erase(unique(val.begin(),val.end()),val.end());
sort(a,a+n);
for(int i=n-1;i>=0;i--)
{
a[i]=lower_bound(val.begin(),val.end(),a[i])-val.begin();
pos[a[i]].push_back(i);
}
int sz=pos[0].size();
pos[0].pop_back();
cout<<1ll*calc(1)*sz%mod;
}
I2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KCnVzaW5nIG5hbWVzcGFjZSBzdGQ7Cgpjb25zdCBpbnQgTj0yNjsKY29uc3QgaW50IG1vZD0xZTkrNzsKaW50IG4sYVtOXSxkcFsoMTw8TildOwp2ZWN0b3I8aW50PnZhbCxwb3NbTl07CgppbnQgY2FsYyhpbnQgbWFzaykKewogICAgaW50ICZyZXM9ZHBbbWFza107CiAgICBpZihyZXMhPS0xKSByZXR1cm4gcmVzOwogICAgcmVzPTA7CiAgICBpbnQgZmlyc3RfYml0PS0xOwogICAgaW50IHNlY29uZF9iaXQ9LTE7CiAgICBmb3IoaW50IGk9MDtpPG47aSsrKQogICAgewogICAgICAgIGlmKG1hc2s+PmkmMSkKICAgICAgICB7CiAgICAgICAgICAgIGlmKGZpcnN0X2JpdD09LTEpIGZpcnN0X2JpdD1pOwogICAgICAgICAgICBlbHNlIGlmKHNlY29uZF9iaXQ9PS0xKSBzZWNvbmRfYml0PWk7CiAgICAgICAgfQogICAgfQogICAgaWYoZmlyc3RfYml0PT1uLTEmJnNlY29uZF9iaXQ9PS0xKSByZXR1cm4gcmVzPTE7CiAgICBlbHNlIGlmKGZpcnN0X2JpdD09c2Vjb25kX2JpdC0xKSByZXM9Y2FsYyhtYXNrLSgxPDxmaXJzdF9iaXQpKTsvLy8ga28geMOieSB0aMOqbSBjw6J5IGTGsOG7m2kgxJHhu4luaCBmaXJzdF9iaXQKICAgIGZvcihpbnQgaWk9MDtpaTx2YWwuc2l6ZSgpO2lpKyspCiAgICB7CiAgICAgICAgZm9yKGludCBqaj1paTtqajx2YWwuc2l6ZSgpO2pqKyspCiAgICAgICAgewogICAgICAgICAgICBpbnQgeD12YWxbaWldOwogICAgICAgICAgICBpbnQgeT12YWxbampdOwogICAgICAgICAgICBpZihfX2djZCh4LHkpIT12YWxbYVtmaXJzdF9iaXRdXSkgY29udGludWU7CiAgICAgICAgICAgIGludCBtdWw9MTsKICAgICAgICAgICAgaWYocG9zW2lpXS5lbXB0eSgpKSBjb250aW51ZTsKICAgICAgICAgICAgbXVsPW11bCpwb3NbaWldLnNpemUoKTsKICAgICAgICAgICAgaW50IGk9cG9zW2lpXS5iYWNrKCk7CiAgICAgICAgICAgIHBvc1tpaV0ucG9wX2JhY2soKTsKICAgICAgICAgICAgaWYocG9zW2pqXS5lbXB0eSgpKQogICAgICAgICAgICB7CiAgICAgICAgICAgICAgICBwb3NbaWldLnB1c2hfYmFjayhpKTsKICAgICAgICAgICAgICAgIGNvbnRpbnVlIDsKICAgICAgICAgICAgfQogICAgICAgICAgICBtdWw9bXVsKnBvc1tqal0uc2l6ZSgpOwogICAgICAgICAgICBpbnQgaj1wb3NbampdLmJhY2soKTsKICAgICAgICAgICAgcG9zW2pqXS5wb3BfYmFjaygpOwogICAgICAgICAgICBpZih4PT15KSBtdWw9KDFsbCptdWwqKG1vZCsxKS8yKSVtb2Q7CiAgICAgICAgICAgIGlmKGZpcnN0X2JpdCE9c2Vjb25kX2JpdC0xJiZpIT1maXJzdF9iaXQrMSkgbXVsPTA7Ly8vIG7hur91IGZpcnN0X2JpdCB2w6Agc2Vjb25kX2JpdCBrbyBsaeG7gW4gbmhhdSBi4bqvdCBideG7mWMgaSBwaOG6o2kgYuG6sW5nIGZpcnN0X2JpdCsxLgogICAgICAgICAgICBpbnQgY3VyX21hc2s9bWFzay0oMTw8Zmlyc3RfYml0KTsvLy8geMOzYSBmaXJzdF9iaXQKICAgICAgICAgICAgY3VyX21hc2srPSgxPDxpKSsoMTw8aik7Ly8vIHRoZW0gxJHhu4luaCBpIHbDoCBqLgogICAgICAgICAgICByZXM9KHJlcysxbGwqY2FsYyhjdXJfbWFzaykqbXVsJW1vZCklbW9kOwogICAgICAgICAgICBwb3NbampdLnB1c2hfYmFjayhqKTsKICAgICAgICAgICAgcG9zW2lpXS5wdXNoX2JhY2soaSk7CiAgICAgICAgfQogICAgfQogICAgcmV0dXJuIHJlczsKfQoKaW50IG1haW4oKQp7CiAgICBpb3NfYmFzZTo6c3luY193aXRoX3N0ZGlvKGZhbHNlKTsKICAgIGNpbi50aWUobnVsbHB0cik7CiAgICBtZW1zZXQoZHAsLTEsc2l6ZW9mIGRwKTsKICAgIGNpbj4+bjsKICAgIGZvcihpbnQgaT0wO2k8bjtpKyspCiAgICB7CiAgICAgICAgY2luPj5hW2ldOwogICAgICAgIHZhbC5wdXNoX2JhY2soYVtpXSk7CiAgICB9CiAgICBzb3J0KHZhbC5iZWdpbigpLHZhbC5lbmQoKSk7CiAgICB2YWwuZXJhc2UodW5pcXVlKHZhbC5iZWdpbigpLHZhbC5lbmQoKSksdmFsLmVuZCgpKTsKICAgIHNvcnQoYSxhK24pOwogICAgZm9yKGludCBpPW4tMTtpPj0wO2ktLSkKICAgIHsKICAgICAgICBhW2ldPWxvd2VyX2JvdW5kKHZhbC5iZWdpbigpLHZhbC5lbmQoKSxhW2ldKS12YWwuYmVnaW4oKTsKICAgICAgICBwb3NbYVtpXV0ucHVzaF9iYWNrKGkpOwogICAgfQogICAgaW50IHN6PXBvc1swXS5zaXplKCk7CiAgICBwb3NbMF0ucG9wX2JhY2soKTsKICAgIGNvdXQ8PDFsbCpjYWxjKDEpKnN6JW1vZDsKfQo=