#pragma GCC optimize("unroll-loops","omit-frame-pointer","inline","rounding-math")//,"signaling-nans")
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
// typedef float16_t fp16;
typedef float fp16;
typedef float fp32;
typedef double fp64;
typedef long long ll;
typedef long double fp128;
typedef double ld;
#define SZ 150003
int n,a[SZ];
const int MOD=1e9+7;
ll qp(ll a,ll b) {
    ll x=1; a%=MOD;
    while(b) {
        if(b&1) x=x*a%MOD;
        a=a*a%MOD; b>>=1;
    }
    return x;
}
const int M=50;
int m,cnt[SZ];
int g[2][1005][1005],t[1005][1005];
#define W 2200
ll fac[SZ],rfac[SZ];
// typedef ld pt[W][W];
typedef complex<ld> cld;
typedef cld ct[W][W];
ct A0,A1,B0,B1,C0,C1,C2,TMP;
template<class T>
void transp(T&s,int k1,int k2) {
    int m=min(k1,k2);
    for(int i=0;i<k1;++i)
        for(int j=0;j<k2;++j) {
            if(i<m&&j<m) {
                if(i<j) swap(s[i][j],s[j][i]);
                continue;
            }
            s[j][i]=s[i][j];
        }
}
int K;
cld w[2][W];
void fftinit() {
    w[0][0]=w[0][K]=1;
    ld ang=2*acos(-1)/K;
    for(int i=1;i<K;++i) w[0][i]=cld(cos(i*ang),sin(i*ang));
    for(int i=0;i<=K;++i) w[1][i]=w[0][K-i];
}
void dft_1d(cld*x,bool v=0) {
    for(int i=0,j=0;i<K;++i) {
        if(i>j) swap(x[i],x[j]);
        for(int l=(K>>1);(j^=l)<l;l>>=1);
    }
    for(int i=2;i<=K;i<<=1) {
        for(int j=0;j<K;j+=i)
            for(int l=0;l<(i>>1);++l) {
                auto t=x[j+l+(i>>1)]*w[v][K/i*l];
                x[j+l+(i>>1)]=x[j+l]-t;
                x[j+l]=x[j+l]+t;
            }
    }
    if(!v) return;
    ld r=ld(1)/K;
    for(int i=0;i<K;++i) x[i]=x[i]*r;
}
void idft_1d(cld*x) {
    dft_1d(x,1);
}
void dft_1d(ct&A,int k1,int k2) {
    K=k2;fftinit();
    for(int i=0;i<k1;++i) dft_1d(A[i]);
}
void idft_1d(ct&A,int k1,int k2) {
    K=k2;fftinit();
    for(int i=0;i<k1;++i) idft_1d(A[i]);
}
void dft(ct&A,int k1,int k2) {
    dft_1d(A,k1,k2);
    transp(A,k1,k2);
    dft_1d(A,k2,k1);
    transp(A,k2,k1);
}
void idft(ct&A,int k1,int k2) {
    idft_1d(A,k1,k2);
    transp(A,k1,k2);
    idft_1d(A,k2,k1);
    transp(A,k2,k1);
}
int A[W][W],B[W][W],X[W][W];
const int BB=32768;
template<class T>
void decomp(T&a,ct&a0,ct&a1,int K1,int K2) {
    for(int i=0;i<K1;++i)
        for(int j=0;j<K2;++j) {
            a[i][j]=(a[i][j]%MOD+MOD)%MOD;
            a0[i][j]=a[i][j]%BB;
            a1[i][j]=a[i][j]/BB;
        }
}
void work(int K1,int K2) {
    decomp(A,A0,A1,K1,K2);
    decomp(B,B0,B1,K1,K2);
    dft(A0,K1,K2);
    dft(A1,K1,K2);
    dft(B0,K1,K2);
    dft(B1,K1,K2);
    for(int i=0;i<K1;++i)
        for(int j=0;j<K2;++j) {
            C0[i][j]=A0[i][j]*B0[i][j];
            C1[i][j]=A0[i][j]*B1[i][j]+A1[i][j]*B0[i][j];
            C2[i][j]=A1[i][j]*B1[i][j];
        }
    idft(C0,K1,K2);
    idft(C1,K1,K2);
    idft(C2,K1,K2);
    for(int i=0;i<K1;++i)
        for(int j=0;j<K2;++j) {
            auto rr=[&](cld u) {
                ll s=round(u.real());
                return s;
            };
            X[i][j]=(rr(C0[i][j])+(rr(C1[i][j])+rr(C2[i][j])*BB)%MOD*BB)%MOD;
        }
    // for(int i=0;i<K1;++i)
    //     for(int j=0;j<K1;++j)
    //         for(int x=0;x<K2;++x)
    //             for(int y=0;x+y<K2;++y)
    //                 (X[i+j][x+y]+=(ll)A[i][x]*B[j][y]%MOD)%=MOD;
}
int getKlog(int s) {
    int u=0;
    while((1<<u)<s) ++u;
    return u;
}
int getK(int s) {
    return 1<<getKlog(s);
}
int main() {
    cin>>n;
    fac[0]=1;
    for(int i=1;i<SZ;++i) fac[i]=fac[i-1]*i%MOD;
    rfac[SZ-1]=qp(fac[SZ-1],MOD-2);
    for(int i=SZ-1;i;--i) rfac[i-1]=rfac[i]*i%MOD;
    // cerr<<rfac[0]<<"+\n";
    for(int i=0;i<n;++i) cin>>a[i],++cnt[a[i]];
    m=n-2;
    ll fc=1;
    for(int i=1;i<=m;++i) fc=fc*i%MOD;
    fc = qp(fc*(m+1),MOD-2)-qp(fc*(m+2),MOD-2);
    ll gg=1;
    for(int i=0;i<n;++i) gg=gg*qp(qp(2,a[i]),MOD-2)%MOD;
    ll aa=0;
    // for(int i=0;i<n;++i) {
    //     for(int j=0;j<(1<<n);++j) {
    //         ll s=0;
    //         for(int k=0;k<n;++k) if(j&(1<<k)) s+=1LL<<a[k];
    //         if(s<=(1LL<<a[i])) aa+=qp(-1,__builtin_popcount(j))*qp((1LL<<a[i])-s,n),aa%=MOD;
    //     }
    // }
    int cu=0,C=0;
    g[0][0][0]=1;
    for(int i=0;i<=50;++i) {
        C^=1;
        for(int j=0;j<=(cu+1)/2;++j) memset(g[C][j],0,sizeof g[0][0]);
        for(int j=0;j<=cu;++j) {
            for(int k=0;k<=n;++k)
                (g[C][(j+1)/2][k]+=g[!C][j][k])%=MOD;
        }
        cu=(cu+1)/2;
        if(!cnt[i]) continue;
        int K1=getK(cnt[i]+cu+1);
        int K2=getK(n+n+1);
        for(int x=0;x<K1;++x)
        for(int y=0;y<K2;++y) A[x][y]=0;
        for(int x=0;x<K1;++x)
        for(int y=0;y<K2;++y) B[x][y]=0;
        for(int x=0;x<=cnt[i];++x) {
            for(int j=0;j<=n;++j)
                A[x][j]=qp((1LL<<i)*x,j)*qp(-1,x)%MOD*rfac[j]%MOD*fac[cnt[i]]%MOD*rfac[x]%MOD*rfac[cnt[i]-x]%MOD;
        }
        for(int x=0;x<=cu;++x) {
            for(int j=0;j<=n;++j)
                B[x][j]=g[C][x][j]*rfac[j]%MOD;
        }
        // for(int x=0;x<=1&&x<=cu;++x)
        //     for(int y=0;y<=n;++y)
        //         cout<<i<<","<<x<<","<<y<<":"<<g[C][x][y]<<"ST+\n";
        work(K1,K2);
        cu+=cnt[i];
        for(int x=0;x<=cu;++x)
            for(int y=0;y<=n;++y) g[C][x][y]=X[x][y]*(ll)fac[y]%MOD;
        ll ca=0;
        for(int x=0;x<=1&&x<=cu;++x)
            for(int y=0;y<=n;++y) {
                ca+=qp(-1,n)*qp(-(1LL<<i),y)*g[C][x][n-y]%MOD*fac[n]%MOD*rfac[y]%MOD*rfac[n-y]%MOD,ca%=MOD;
                // aa+=cnt[i]*qp((1LL<<i)-s,n),aa%=MOD;
            }
        // for(int x=0;x<=1&&x<=cu;++x)
        //     for(int y=0;y<=n;++y)
        //         cout<<i<<","<<x<<","<<y<<":"<<g[C][x][y]<<"+\n";
        aa+=ca*cnt[i]; aa%=MOD;
    }
    aa=aa*fc%MOD;
    aa=aa*gg%MOD;
    aa=(1-aa)%MOD;
    aa=(aa%MOD+MOD)%MOD;
    cout<<aa<<"\n";
}