uoj
bzoj
luogu

sol

根据(Lucas)定理，(binom nm mod 2=binom{n%2}{m%2}timesbinom{n/2}{m/2}mod 2)。

由于(binom{n%2}{m%2})的取值只可能是(0)或(1)，以为我们希望(binom nm=1mod 2)，所以(binom{n%2}{m%2})应该始终取值为(1)。因为(binom 00=binom 10=binom 11=1,binom 01=0)，所以(binom{n%2}{m%2})始终为(1)其实就要求了(n)在每个二进制位上的值都不小于(m)在那位上的值。
这不就是说(m)是(n)的子集吗？
所以这个题就很简单了吧。枚举子集算当前位的(dp)值，复杂度(O(3^{log a_i}))。
这个复杂度假的不行啊。
考虑一些优化。我们相当于是要支持一个数据结构支持插入一个数，或查询某个数的所有子集。上面(O(3^{log a_i}))的做法中，插入和查询一者的复杂度是(O(3^{log a_i}))，而另一者是线性的。这样很不优雅，我们考虑尽量均摊这个复杂度。
开桶，记(t_i)表示前(9)位是(i)的前(9)位的超集，后(9)位与(i)的后(9)位相同的数之和。这样均摊每(2^9)次插入和查询的复杂度是(O(3^9))，所以总复杂度就是(O(6^9))。

code

#include<cstdio>
#include<algorithm>
using namespace std;
int gi(){
    int x=0,w=1;char ch=getchar();
    while ((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
    if (ch=='-') w=0,ch=getchar();
    while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
    return w?x:-x;
}
const int mod = 1e9+7;
int n,ans,t[1<<18];
void mdf(int x,int y){
    int a=x&(~511),b=x&511;(t[b]+=y)%=mod;
    for (int c=a;c;c=(c-1)&a) (t[c|b]+=y)%=mod;
}
int qry(int x){
    int a=x&(~511),b=(x&511)^511,res=t[a|511];
    for (int c=b;c;c=(c-1)&b) (res+=t[a|(c^511)])%=mod;
    return res;
}
int main(){
    n=gi();
    for (int i=1;i<=n;++i){
        int a=gi(),f=qry(a)+1;
        ans=(ans+f)%mod;mdf(a,f);
    }
    printf("%dn",(ans-n+mod)%mod);return 0;
}