题目内容

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

具体而言，给定一个长度为 $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$ 后的结果）。