异或三元组

题目描述

Y 同学得到了一个长度为 $N$ 的正整数序列 $A = \{a_1, a_2, \dots, a_N\}$。

他想知道，在这个序列中，有多少个三元组下标 $(i, j, k)$ 能够同时满足以下所有条件：

1. 下标有序：$1 \le i < j < k \le N$。
2. 异或和为零：$a_i \oplus a_j \oplus a_k = 0$。
3. 两两异或的位数限制：
   • $\text{popcount}(a_i \oplus a_j) \le 2$
   • $\text{popcount}(a_i \oplus a_k) \le 2$
   • $\text{popcount}(a_k \oplus a_j) \le 2$

其中 $\oplus$ 表示按位异或运算，$\text{popcount}(x)$ 表示整数 $x$ 在二进制表示下 $1$ 的个数。

请你计算满足上述条件的三元组数量，并将结果对 $10^9 + 7$ 取模后输出。

输入格式

本题包含多组测试数据。

第一行输入一个整数 $T$，表示测试数据的组数。

对于每组测试数据： 第一行输入一个正整数 $N$，表示序列的长度。 第二行输入 $N$ 个正整数 $a_1, a_2, \dots, a_N$，表示序列中的元素。

输出格式

对于每组测试数据，输出一行一个整数，表示满足条件的三元组数量对 $10^9 + 7$ 取模后的结果。

样例

样例输入 #1

2
3
1 1 1
5
1 2 3 4 5

样例输出 #1

0
2

数据范围与约定

对于 $100\%$ 的数据，保证：

• $1 \le T \le 10$
• $1 \le N \le 3 \times 10^5$
• $1 \le a_i \le 2^{120}$

特殊性质说明：

• A：对于任意 $a_i$，满足 $\text{popcount}(a_i)=1$。
• B：满足 $a_i \ge 2^{30}$ 且数据随机生成。

注意：本题中 $a_i$ 的范围较大，无法使用标准的 64 位整数存储。你需要使用 __int128 或其他高精度方式进行处理。使用 __int128 时需自行实现输入输出功能。