P13818 「LDOI R3」泡泡抗特

somewhere $\ $ over $\ $ the rainbow $\ $ way up $\ $ high. there's a land $\ $ that i heard of once $\ $ in a lullaby. only blue. only blue. $\ $ 愛讓人，好憂鬱。 我的心。我的心。藍藍的。

给定长度为 $n$ 的正整数序列 $a_1, a_2, \ldots,a_n$。 求满足以下条件的正整数三元组 $(i,j,k)$ 的个数： - $1\le i < j < k \le n$。 - $\mathrm{popcount}(a_i\oplus a_j) \le 2$。 - $\mathrm{popcount}(a_i\oplus a_k) \le 2$。 - $\mathrm{popcount}(a_k\oplus a_j) \le 2$。 - $a_i \oplus a_j \oplus a_k = 0$。 你只需要输出答案模 $10^9 + 7$ 的值。 其中 $\oplus$ 代表二进制下的按位异或运算。 ::::info[$\mathrm{popcount}$ 是什么？] 对于正整数 $x$，我们定义 $\mathrm{popcount}(x)$ 为 $x$ 在二进制下 $1$ 的个数。 例如，$11 = (1011)_2$，因此 $\mathrm{popcount}(11) = 3$。 ::::

**本题有多组测试数据。** 每个输入数据第一行有一个整数 $T$。 每组测试第一行输入一个正整数 $n$。 每组测试第二行输入 $n$ 个正整数，第 $i$ 个正整数代表 $a_i$。

每组测试输出一行一个整数，代表答案模 $10^9 + 7$ 的值。

#### 【样例解释】 - 第一组输入没有合法的三元组。 - 第二组输入有 $(i, j, k) = (1,2,3),(1,4,5)$ 两组合法。 #### 【数据范围与约定】 对于 $100\%$ 的数据，保证： - $1\le n\le 3\times 10^5$， - $1\le a_i\le 2^{120}$， - $1\le T\le 10$。 ::cute-table{tuack} |$\text{Subtask}$| $n\le$ | $a_i\le$ | 特殊性质 | 分数 | |:-:|:-:|:-:|:-:|:-:| | 1 | $10$ | $2^{30}$ | 无 | $10$ | | 2 | $2000$ | $2^{30}$ | 无 | $15$ | | 3 | $10^4$ | $2^{30}$ | 无 | $15$ | | 4 | $10^5$ | $2^{60}$ | A | $5$ | | 5 | $10^5$ | $2^{60}$ | B | $5$ | | 6 | $10^5$ | $2^{60}$ | 无 | $20$ | | 7 | $3\times 10^5$ | $2^{120}$ | 无 | $30$ | 特殊性质 A：对于任意 $a_i$，满足 $\mathrm{popcount}(a_i)=1$。 特殊性质 B：满足 $a_i \ge 2^{30}$ 且数据随机。 #### 【其它注意事项】 **本题输入量较大，请使用较快的 IO 方式。** 本题 $a_i$ 的范围较大，您可以使用 `__int128`。 `__int128` 可以存储大致 $2^{127}$ 左右的数据，你可以用它存储 $a_i$。但是，它并不支持传统的输入输出，因此我们提供了读入模板，你可以调用该函数读入 `__int128`。 ```cpp void redi (__int128& ret) { ret = 0; int f = 1; char ch = getchar(); while (ch < '0' || ch > '9') {if (ch == '-') f = -f; ch = getchar();} while (ch >= '0' && ch