D. Not Quite Lee

在$bb$中选出$n\{n\}$个数$a_{i}a\_i$，这个子序列是好的当且仅当能找到满足如下条件的$x\{x\}$：

$\frac{a_1(2\ast x_1+a_1-1)}{2}+\frac{a_2(2\ast x_2+a_2-1)}{2}+\mathrm{.}\mathrm{.}\mathrm{.}+\frac{a_n(2\ast x_n+a_n-1)}{2}=0\{\backslash frac\{a\_1(2*x\_1+a\_1-1)\}\{2\}+\backslash frac\{a\_2(2*x\_2+a\_2-1)\}\{2\}+...+\backslash frac\{a\_n(2*x\_n+a\_n-1)\}\{2\}=0\}$，$\{x_i\mathrm{\mid }{x}_i\in \mathbb{Z}\}\{\backslash \{x\_i|x\_i\backslash in\; \backslash Z\backslash \}\}$

$(2\ast x_1-1)\ast a_1+(2\ast x_2-1)\ast a_2+\mathrm{.}\mathrm{.}\mathrm{.}+(2\ast x_n-1)\ast a_n=-a_1^2-a_2^2-\mathrm{.}\mathrm{.}\mathrm{.}-a_n^2\{(2*x\_1-1)*a\_1+(2*x\_2-1)*a\_2+...+(2*x\_n-1)*a\_n=-a\_1^2-a\_2^2-...-a\_n^2\}$，$\{x_i\mathrm{\mid }{x}_i\in \mathbb{Z}\}\{\backslash \{x\_i|x\_i\backslash in\; \backslash Z\backslash \}\}$

$x_1\ast a_1+x_2\ast a_2+\mathrm{.}\mathrm{.}\mathrm{.}+x_n\ast a_n=-a_1^2-a_2^2-\mathrm{.}\mathrm{.}\mathrm{.}-a_n^2\{x\_1*a\_1+x\_2*a\_2+...+x\_n*a\_n=-a\_1^2-a\_2^2-...-a\_n^2\}$，$\{x_i\mathrm{\mid }{x}_i\mathrm{\%}2==1\}\{\backslash \{x\_i|x\_i\backslash \%2==1\; \backslash \}\}$

$(x_1+a_1)\ast a_1+(x_2+a_2)\ast a_2+\mathrm{.}\mathrm{.}\mathrm{.}+(x_n+a_n)\ast a_n=0\{(x\_1+a\_1)*a\_1+(x\_2+a\_2)*a\_2+...+(x\_n+a\_n)*a\_n=0\}$，$\{x_i\mathrm{\mid }{x}_i\mathrm{\%}2==1\}\{\backslash \{x\_i|x\_i\backslash \%2==1\; \backslash \}\}$

$x_1\ast a_1+x_2\ast a_2+\mathrm{.}\mathrm{.}\mathrm{.}+x_n\ast a_n=0\{x\_1*a\_1+x\_2*a\_2+...+x\_n*a\_n=0\}$，$\{x_i\mathrm{\mid }{a}_i\mathrm{为}\mathrm{奇}\mathrm{数}\mathrm{则}{x}_i\mathrm{为}\mathrm{偶}\mathrm{数}\mathrm{，}\mathrm{反}\mathrm{之}{x}_i\mathrm{为}\mathrm{奇}\mathrm{数}\}\{\backslash \{x\_i|a\_i为奇数则x\_i为偶数，反之x\_i为奇数\; \backslash \}\}$

1. 如果存在多个$a_i\{a\_i\}$为奇数，那么我们取一个奇数的$a_k\{a\_k\}$，其它的奇数$a_i\{a\_i\}$对应的$x_i\{x\_i\}$制为0，对每个偶数$a_j\{a\_j\}$，我们一定能解得使得$x_j\ast a_j+x_{kj}\ast a_k=0\{x\_j*a\_j+x\_\{kj\}*a\_k=0\}$，将所有的$x_{kj}\{x\_\{kj\}\}$求和得到$x_k\{x\_k\}$使得等式成立。
2. 假设这个$n\{n\}$个数都是偶数，不断提取公因子$2\{2\}$，最后为常数为奇数的项有$res\{res\}$个。如果$res\{res\}$为奇数，将这些项合并成一个项后就是一个奇数，而其它项都是偶数，那么所有项之和一定不为0；反之可以任取$res\{res\}$中的两项去抵消其它项。

第2点的例子：

a_1=5 	a_2=9 	a_3=2*3
x_1=3*9 x_2=3*5	x_3=-5*9

a_1=5	  a_2=9 	a_3=2*2*7
x_1=3*7*9 x_2=5*7	x_3=-5*9

a_1=5		  a_2=9 		a_3=2*3 	a_4=2*2*7
x_1=3*9+3*7*9 x_2=3*5+5*7	x_3=-5*9	x_4=-5*9

对每个数按因子$2\{2\}$的个数$i\{i\}$分类，因子$2\{2\}$的个数为$i\{i\}$的数有$cntcnt$个，因子$2\{2\}$的个数大于$i\{i\}$的数有$sum\{sum\}$个，$i\{i\}$从$30\{30\}$到$i\{i\}$枚举，因子$2\{2\}$的个数为$i\{i\}$的数选出偶数个，选法有$\frac{2^{cnt}}{2}-1\{\backslash frac\{2^\{cnt\}\}\{2\}-1\}$（选出奇数个的方案数=选出偶数个的方案数，选出偶数个的方案包含了空集），然后因子$2\{2\}$的个数大于$i\{i\}$的每个数可选可不选，选法有种$2^{sum}\{2^\{sum\}\}$，总的贡献为$(2^{cnt-1}-1)\ast 2^{sum}\{(2^\{cnt-1\}-1)*2^\{sum\}\}$。因子$2\{2\}$的个数为$1\{1\}$的数是奇数，每个数可选可不选（空集除外），总的贡献为$(2^{cnt}-1)\ast 2^{sum}\{(2^\{cnt\}-1)*2^\{sum\}\}$

code:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn=2e5+7,mod=1e9+7;
ll qpow(ll a, ll b) {
	ll ans = 1;
	while (b) {
		if (b & 1)
			ans = ans * a % mod;
		a = a * a % mod;
		b >>= 1;
	}
	return ans;
}
inline void solve() {
	int n;
	cin>>n;
	vector<int>b(32);
	for(int i=1,x; i<=n; ++i) {
		cin>>x;
		int cnt(0);
		while(x%2==0) {
			x/=2;
			++cnt;
		}
		++b[cnt];
	}
	ll ans(0);
	int cc(0);
	for(int i=30; ~i; --i) if(b[i]) {
		if(i) ans+=qpow(2,cc)*(qpow(2,b[i]-1)-1)%mod;
		else ans+=qpow(2,cc)*(qpow(2,b[i])-1)%mod;
		if(ans>=mod) ans-=mod;
		cc+=b[i];
	}
	cout<<ans<<'\n';
}
int main() {
	cin.sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
	int _=1;
//	cin>>_;
	while(_--) solve();
	return 0;
}