好题啊！最喜欢这种思路层层递进的题了。
首先从最终形态的角度入手分析。建立一棵合并树，每次合并两个数的时候就新建一个节点，令这个节点为合并的两个节点的父亲。那么显然一个点对答案的贡献系数就是 \(2^{-\text{其在合并树中的深度}}\)。更具体地不妨设 \(B>A\)，最终被划分在 \(A\) 对应的数中的下标集合为 \(S\)，\(B\) 中对应的数的下标集合为 \(T\)，\(i\) 点的深度为 \(d_i\)，则
这样还是不好处理。不妨设 \(a\) 数组是有序的，那么可以分析得以下性质：
- 选 \(S\) 的是一段前缀，选 \(T\) 的是一段后缀。证明显然。
- 假设 \(S\) 中包含了前 \(i\) 个元素，那么 \(d_j=\begin{cases}j&(j<i)\\j-1&(j=i)\\n-j&(j=i+1)\\n-j+1&(j>i+1)\end{cases}\)，这是因为对于 \(T\) 的部分，如果存在四个数 \(a,b,c,d(a<b<c<d)\)，满足我们先合并 \(a,b\)，再合并 \(c,d\)，再合并 \(\dfrac{a+b}{2},\dfrac{c+d}{2}\)，那么总和为 \(\dfrac{a+b+c+d}{4}\)，而如果我们先合并 \(a,b\)，再合并 \(\dfrac{a+b}{2},c\)，再合并 \(\dfrac{a+b}{4}+\dfrac{c}{2},d\)，总和为 \(\dfrac{a+b}{8}+\dfrac{c}{4}+\dfrac{d}{2}\)，因为 \(a+b<2d\)，所以后者更大。
这样我们有了 \(n^2\) 的做法：暴力枚举分界点计算。可以主席树优化到 \(n\log^2n\)，如果数据范围少个 \(0\) 那还有过的可能，但是出题人开 \(10^6\) 显然就是为了刻意卡掉这个做法，我们只能另辟蹊径。
考虑计算分界点由 \(i\) 改到 \(j\) 的贡献之差：
其中 \(b_i=a_i-a_{i-1}\)。
如果 \(j\le\dfrac{n}{2}\)，那么容易注意到中间那一项是大于 \(0\) 的，也就是说只要 \(\dfrac{b_i}{2^{i-1}}\le\dfrac{b_j}{2^{n-j+1}}\) 就一定有 \(D\ge 0\)，而如果 \(j\ne\dfrac{n}{2}-30\) 且 \(b_i>0\)，这个条件就一定满足，因为 \(b_i\le 10^9\)，并且 \(\dfrac{1}{2^{i-1}}\) 一定至少是 \(\dfrac{1}{2^{n-j+1}}\) 的 \(2^{30}\) 倍，因此 \(i\le\dfrac{n}{2}-30\) 的部分一定是越靠前越好，如果 \(i\le\dfrac{n}{2}-30\) 的部分没有 \(b_i\ne 0\) 的位置就在 \([\dfrac{n}{2}-30,\dfrac{n}{2}]\) 中找，等价的实现方式是找前 \(30\) 个 \(b_i\ne 0\) 的位置 check。对于后一半也是同样的分析方法，实现是找最后 \(30\) 个 \(b_i\ne 0\) 的位置 check。
这样 check 次数是 \(O(\log V)\) 的，可以通过。
const int MAXN=1e6+50;
const int MOD=1e9+7;
int qpow(int x,int e){int ret=1;for(;e;e>>=1,x=1ll*x*x%MOD)if(e&1)ret=1ll*ret*x%MOD;return ret;}
int n,a[MAXN+5],res[MAXN+5],x[MAXN+5];
void check(int p){
for(int i=0;i<=n+50;i++)x[i]=0;
for(int i=1;i<=p;i++){
int coef=(i==p)?(i-1):i;
for(int j=0;j<30;j++)x[j-coef+n]-=(a[i]>>j&1);
}
for(int i=p+1;i<=n;i++){
int coef=(i==p+1)?(n-i):(n-i+1);
for(int j=0;j<30;j++)x[j-coef+n]+=(a[i]>>j&1);
}
for(int i=0;i<=n+50;i++){
while(x[i]<0)x[i+1]--,x[i]+=2;
while(x[i]>=2)x[i+1]++,x[i]-=2;
}
// printf("check %d\n",p);
// for(int i=0;i<=n+50;i++)printf("%d%c",x[i]," \n"[i==n+50]);
for(int i=n+50;~i;i--)if(x[i]!=res[i]){
if(x[i]>res[i]){for(int j=0;j<=n+50;j++)res[j]=x[j];}
return;
}
}
void solve(){
scanf("%d",&n);for(int i=0;i<=n+50;i++)res[i]=0;
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
sort(a+1,a+n+1);
int cnt=32;for(int i=2;i<=n&&cnt;i++)if(a[i]!=a[i-1])check(i-1),--cnt;
cnt=32;for(int i=n;i>=2&&cnt;i--)if(a[i]!=a[i-1])check(i-1),--cnt;
int ans=0;
for(int i=0;i<=n+50;i++)if(res[i])ans=(ans+qpow(2,i-n+MOD-1))%MOD;
printf("%d\n",ans);
}
int main(){
int qu;scanf("%d",&qu);while(qu--)solve();
return 0;
}