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$ 的值。

输入输出样例 #1

输入 #1

2
3
1 1 1
5
1 2 3 4 5

输出 #1

0
2

说明/提示

【样例解释】

• 第一组输入没有合法的三元组。
• 第二组输入有 $(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}

特殊性质 A：对于任意 $a_i$，满足 $\mathrm{popcount}(a_i)=1$。
特殊性质 B：满足 $a_i \ge 2^{30}$ 且数据随机。

【其它注意事项】

本题输入量较大，请使用较快的 IO 方式。

本题 $a_i$ 的范围较大，您可以使用 __int128。

__int128 可以存储大致 $2^{127}$ 左右的数据，你可以用它存储 $a_i$。但是，它并不支持传统的输入输出，因此我们提供了读入模板，你可以调用该函数读入 __int128。

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 <= '9') ret = ret * 10 + ch - '0', ch = getchar();
    ret *= f;
} // 调用 redi(x) 以读入变量 x。