449D - Jzzhu and Numbers - CodeForces Solution

#include<bits/stdc++.h>
using namespace std;
using INT = long long;
const int NN = 1e6 + 100;
int dp[NN][21],a[NN],p[NN];
int main() {
#ifndef ONLINE_JUDGE
	freopen("in.in", "r", stdin);
#endif
	  int n,mod=1000000007;
	  cin>>n;
	  for(int i=1;i<=n;i++) scanf("%d",a+i),dp[a[i]][0]++;
	  for(int j=1;j<=20;j++){
	  	for(int i=0;i<NN;i++){
			dp[i][j]=dp[i][j-1];
	  		if(i&(1<<j-1)) continue;
	  		if(i+(1<<j-1)<NN) dp[i][j]+=dp[i+(1<<j-1)][j-1];
		  }
	  }
	  p[0]=1;
	  for(int i=1;i<NN;i++) p[i]=p[i-1]*2%mod;
	  int ans=0;
	  for(int i=0;i<NN;i++){
	  	int id=p[dp[i][20]]-1;
	  	int k=__builtin_popcount(i);
	  	if((k%2)) id=mod-id;
	  	ans=(ans+id)%mod;
	  }
	  printf("%d\n",ans);
	  
	return 0;
}