题目描述

新学期伊始，“百度之星”蛇小弟选修了一门深奥且神秘的大学核心课程——《奶龙主义原理》。这门课由鼎鼎大名的彭阳老师亲自授课。

期末考试终于到来，彭阳老师有着一套非常独特的评分机制。在他的心目中，班里的 $n$ 名学生每个人都有个“最高印象分” $a_{i}$。按照彭阳老师的习惯，如果一个学生平时和他关系很好，那么该学生就能直接获得满分 $a_{i}$。

然而，在最终录入成绩时，彭阳老师决定贯彻奶龙主义的“混沌与随机”精神。对于第 $i$ 名学生，彭阳老师并没有直接根据关系给分，而是在整数区间 $[0,a_{i}]$ 中等概率且独立地随机生成了一个最终成绩 $b_{i}$。显然，只有当摇出的 $b_{i} = a_{i}$ 时，这名学生才算是体验到了“关系好”的待遇。

作为深谙奶龙主义核心教义的优秀学生，蛇小弟深知，整个班级的“奶龙能量场”必须保持守恒。具体来说，只有当全班同学实际最终成绩的异或和，等于所有人都和老师关系好（即全员拿满分）时的异或和时，奶龙能量场才处于稳定状态，不会发生崩塌。换句话说，必须满足如下等式：

$$ b_{1}\oplus b_{2}\oplus \dots \oplus b_{n} = a_{1}\oplus a_{2}\oplus \dots \oplus a_{n}. $$

其中 $\oplus$ 表示按位异或（XOR）运算。

本题中，异或运算正式定义如下：对于两个非负整数 $x,y$，设它们的二进制展开分别为

$$ x = \sum_{k\geq 0}x_{k}2^{k},\quad y = \sum_{k\geq 0}y_{k}2^{k}, $$

其中 $x_{k},y_{k}\in \{0,1\}$，且只有有限多个二进制位为1。定义

$$ x\oplus y = \sum_{k\geq 0}z_{k}2^{k},\quad z_{k} = (x_{k} + y_{k})\bmod 2. $$

也就是说，在每一个二进制位上，若 $x$ 与 $y$ 的该位不同，则结果该位为1；否则结果该位为0。

多个整数的异或和按该二元运算依次计算。异或运算满足结合律和交换律，因此计算顺序不影响结果。

蛇小弟现在非常担心能量场崩塌。请你帮他计算，在彭阳老师的随机给分机制下，班级奶龙能量场保持稳定的概率是多少？

输入格式

第一行包含一个正整数 $T$（$1\leq T\leq 10^{5}$），表示测试数据组数。

对于每组测试数据：

• 第一行包含一个正整数 $n$（$1\leq n\leq 2\times 10^{5}$），表示选修《奶龙主义原理》的学生人数。
• 第二行包含 $n$ 个整数 $a_{1},a_{2},\ldots ,a_{n}$（$0\leq a_{i}\leq 10^{9}$），分别表示每位同学的最高印象分。

保证所有测试数据中 $n$ 的总和不超过 $2\times 10^{6}$。

输出格式

对于每组测试数据，输出一行一个整数，表示能量场保持稳定的概率。

显然该概率可以表示为一个有理数 $\frac{P}{Q}$，且 $\gcd(P,Q) = 1$。为了避免精度误差，请你输出 $P\cdot Q^{-1} \bmod 10^9 + 7$ 的值。

其中 $Q^{-1}$ 表示 $Q$ 在模 $10^9 + 7$ 意义下的乘法逆元。

样例

输入

1
3
1 2 3

输出

250000002

说明

对于样例一：

$$ a_{1}\oplus a_{2}\oplus a_{3} = 1\oplus 2\oplus 3 = 0. $$

彭阳老师会分别从 $[0,1]$、$[0,2]$、$[0,3]$ 中随机生成 $b_{1},b_{2},b_{3}$，因此总共有

$$ (1 + 1)(2 + 1)(3 + 1) = 24 $$

种等概率的结果。

要使奶龙能量场保持稳定，需要满足

$$ b_{1}\oplus b_{2}\oplus b_{3} = 0. $$

合法的三元组共有 6 个：

$$ (0,0,0),\ (0,1,1),\ (0,2,2),\ (1,0,1),\ (1,1,0),\ (1,2,3). $$

因此概率为

$$ \frac{6}{24} = \frac{1}{4}. $$

在模 $10^9+7$ 意义下，$4^{-1} \equiv 250000002$，所以样例输出为 250000002。