最近在学集合幂级数,突然想到这个题.

记$F(S)$为选出一个合法子序列且or和为$S$的方案数,$G(S)$为数$S$的出现次数.

则有,$F=\exp G$

组合意义上,即无序选出若干个元素and和为0(这里集合幂级数的乘法定义为子集卷积,以满足and结果为0的要求)

集合幂级数怎么做exp?

所以这题该叫[模板]集合幂级数exp

考虑子集卷积的做法:转集合占位幂级数$F(|S|,S)$ 然后每个$|S|$分别做FMT,然后$C(i+j,s)\leftarrow ^+A(i,s)*B(j,s)$ ,即对于每个$s$,$F(0..n,s)$这个形式幂级数的卷积.最后每个$|S|$分别IFMT回去.

那么exp即每个$s$,$F(0..n,s)$这个形式幂级数的exp.$n$很小(这里$n$是指维度)暴力exp即可.

复杂度$O(2^nn^2)$ (写个多项式exp也没用,转集合占位幂级数再FMT就得这个复杂度了)

const int MAXN = 18,mod=1e9+7;
ll Qpow(ll a,ll p)
{
    ll res=1;
    while(p){if(p&1)res=res*a%mod;a=a*a%mod,p>>=1;}
    return res;
}
inline int S(int x){return x<mod?x:x-mod;}
int tf[MAXN+1][1<<MAXN],tg[MAXN+1][1<<MAXN], f[1<<MAXN],cnt[1<<MAXN];
ll inv[MAXN+1];
void FMT(int* a,int len)
{
    for(int cur=1;cur<len;cur<<=1)
        for(int j=0;j<len;j+=cur<<1)
            for(int k=0;k<cur;++k)a[j+cur+k]=S(a[j+cur+k]+a[j+k]);
}
void IFMT(int* a,int len)
{
    for(int cur=1;cur<len;cur<<=1)
        for(int j=0;j<len;j+=cur<<1)
            for(int k=0;k<cur;++k)a[j+cur+k]=S(a[j+cur+k]-a[j+k]+mod);
}

bool vis[1<<MAXN|1];
int phi[1<<MAXN|1],pri[1<<MAXN|1];
void sieve(int n)
{
    int cnt=0;
    vis[1]=1,phi[1]=1;
    for(int i=2;i<=n;++i)
    {
        if(!vis[i])pri[++cnt]=i,phi[i]=i-1;
        for(int j=1;j<=cnt&&i*pri[j]<=n;++j)
        {
            vis[i*pri[j]]=1;
            if(i%pri[j]==0){phi[i*pri[j]]=phi[i]*pri[j];break;}
            phi[i*pri[j]]=phi[i]*phi[pri[j]];
        }
    }
}
int main()
{
    int L=read();
    for(int i=1;i<=L;++i)++f[read()];
    int c0=f[0];
    f[0]=0;
    const int n=18;
    inv[0]=inv[1]=1;
    for(int i=2;i<=n;++i)inv[i]=(mod-mod/i)*inv[mod%i]%mod;//,printf("%d*%lld=%lld\n",i,inv[i],i*inv[i]%mod);
    sieve(1<<n);
    for(int i=1;i<(1<<n);++i)cnt[i]=cnt[i&(i-1)]+1;
    for(int s=0;s<(1<<n);++s)tg[cnt[s]][s]=f[s];
    for(int i=0;i<=n;++i)
    {
        FMT(tg[i],1<<n);
        for(int s=0;s<(1<<n);++s)tg[i][s]=ll(tg[i][s])*i%mod;
    }
    for(int i=0;i<=n;++i)
    {
        if(i)
            for(int s=0;s<(1<<n);++s)tf[i][s]=tf[i][s]*inv[i]%mod;
        else
            for(int s=0;s<(1<<n);++s)tf[i][s]=1;
        for(int j=0;j<=n-i;++j)
            for(int s=0;s<(1<<n);++s)
                tf[i+j][s]=(tf[i+j][s]+ll(tf[i][s])*tg[j][s])%mod;
    }
    for(int i=0;i<=n;++i)IFMT(tf[i],1<<n);
    for(int s=0;s<(1<<n);++s)f[s]=tf[cnt[s]][s];
    ll ans=0;
    for(int s=0;s<(1<<n);++s)ans=(ans+ll(phi[1+s])*f[s])%mod;
    printf("%lld\n",ans*Qpow(2,c0)%mod);
    return 0;
}