解题思路

本题要求统计下标四元组 $(i,j,k,l)$ 满足 $1 \le i < j < k < l \le n$ 且 $c_i + c_j = c_k \oplus c_l$ 的数量。直接四重循环枚举的时间复杂度为 $O(n^4)$，无法承受 $n \le 10^4$ 的数据范围。

注意到序列中的值不超过 $100$，因此 $c_i+c_j$ 的最大值为 $200$，$c_k \oplus c_l$ 的最大值不超过 $127$（因为 $100$ 的二进制为 1100100，异或结果不超过 $127$）。我们可以利用元素大小关系的对称性，通过“隔断” $j$ 与 $k$ 来降低复杂度：

1. 预处理右侧异或值：将数组从 $j+1$ 到 $n$ 的部分视为右侧候选 $k,l$。我们维护一个计数数组 cnt，$cnt[x]$ 表示在当前 $j$ 的右侧（即 $j+1 \le k < l \le n$）有多少对 $(k,l)$ 满足 $c_k \oplus c_l = x$。初始时令 $j=2$，此时右侧为下标 $3 \sim n$，枚举所有 $p,q$ 满足 $2 < p < q \le n$（实际上是 $p$ 从 $j+1$ 到 $n$，$q$ 从 $p+1$ 到 $n$）并把对应异或值放入 cnt 中。
2. 枚举 $j$ 并累加答案：我们从 $j=2$ 扫描到 $n-1$（因为 $k,l$ 至少需要两个位置）。对于当前的 $j$，右侧 cnt 已经存储了所有满足 $k > j$ 的 $(k,l)$ 对。此时枚举所有 $i$ 满足 $1 \le i < j$，计算和 $s = c_i + c_j$，然后答案累加 cnt[s]，并对 $10^9+7$ 取模。
3. 移动 $j$ 并更新 cnt：当 $j$ 向右移动至 $j+1$ 时，原来在右侧的 $c_j$ 现在变为左侧元素，因此我们需要从 cnt 中除去所有包含 $c_j$ 的 $(j, l)$ 对（$l$ 从 $j+1$ 到 $n$）。具体操作：对于所有 $i = j+1 \sim n$，我们将 cnt[c_j ^ c_i] 的值减 $1$。这样 cnt 就正确地表示了新 $j$ 右侧的异或值计数。

题目内容

在探索一座古代遗迹时，你发现了一串神秘的数字序列。遗迹机关要求你统计所有满足特殊等式的四元组数量，只有输入正确结果才能继续前进。

具体而言，给定一个长度为 $n$ 的整数序列 $c_1, c_2, \ldots, c_n$，你需要计算出有多少个下标四元组 $(i, j, k, l)$ 满足 $1 \le i < j < k < l \le n$，并且等式

成立，其中 $\oplus$ 表示按位异或运算。

由于答案可能非常大，请将结果对 $10^9+7$ 取模后输出。

序列的长度 $n$ 不超过 $10^4$，序列中的每个整数不小于 $1$ 且不大于 $100$。

输入描述

第一行包含一个整数 $n$，表示序列的长度。 第二行包含 $n$ 个空格分隔的整数，依次表示 $c_1, c_2, \ldots, c_n$。

输出描述

输出一个整数，表示满足条件的四元组数量对 $10^9+7$ 取模后的结果。

样例1

输入

4
1 2 1 2

输出

1

说明

序列为 $[1, 2, 1, 2]$，长度为 4，唯一的四元组是 $(1,2,3,4)$。 计算得 $c_1+c_2=1+2=3$，$c_3 \oplus c_4=1 \oplus 2=3$，等式成立，因此满足条件的四元组数量为 1，对 $10^9+7$ 取模后仍为 1。

样例2

输入

5
1 2 1 2 1

输出

3

说明

序列为 $[1, 2, 1, 2, 1]$，长度为 5，所有可能的四元组共有 $\binom{5}{4}=5$ 个。 其中满足 $c_i+c_j=c_k \oplus c_l$ 的有：

• $(1,2,3,4)$：$c_1+c_2=1+2=3$，$c_3 \oplus c_4=1 \oplus 2=3$；
• $(1,2,4,5)$：$c_1+c_2=3$，$c_4 \oplus c_5=2 \oplus 1=3$；
• $(2,3,4,5)$：$c_2+c_3=2+1=3$，$c_4 \oplus c_5=2 \oplus 1=3$。 其余四元组均不满足条件，故答案为 3。

样例3

输入

4
1 1 1 1

输出

0

说明

序列为 $[1, 1, 1, 1]$，唯一的四元组是 $(1,2,3,4)$。 计算得 $c_1+c_2=1+1=2$，$c_3 \oplus c_4=1 \oplus 1=0$，$2 eq 0$，等式不成立。 因此没有符合条件的四元组，输出 0（这也是模 $10^9+7$ 后的结果）。