题目背景

这是 $CSP-J$ 模拟赛的 $T3$ 。

题目描述

$Alice$ 有一个长度为 $n$ 的序列 ${a_1,a_2,...,a_n}$ ，$Alice$ 想知道有多少组满足条件的四元组 $(b_1,b_2,b_3,b_4)$ 满足 $1 \le b_1 < b_2 < b_3 < b_4 \le n$ 并且 $ a_{b_1} \oplus a_{b_2} \oplus a_{b_3} \oplus a_{b_4}=0 $ 。

$\oplus$ 表示按位异或运算。

输入格式

输入两行。

第一行一个整数 $n$ 表示序列长度。

第二行 $n$ 个整数，第 $i$ 个整数 $a_i$ 表示数组中第 $i$ 个元素的值。

输出格式

输出一行。

输出一个整数表示四元组个数。

样例 #1

样例输入 #1

6
1 3 0 0 2 2

样例输出 #1

5

样例 #2

样例输入 #2

10
3 4 5 6 7 5 3 0 1 1

样例输出 #2

29

提示

样例解释】：

对于第一个样例，四元组包括: {1,2,3,5},{1,2,3,6},{1,2,4,5},{1,2,4,6},{3,4,5,6} 共 $5$ 个。

数据范围】：

对于 $20\%$ 的数据，满足 $n \le 100,a_i \le 1000$ 。

对于另外 $20\%$ 的数据，满足 $n \le 1000,a_i \le 1000$ 。

对于另外 $20\%$ 的数据，满足 $n \le 5000,a_i \le 1000$ 。

对于全部数据，满足 $4 \le n \le 5000, 0\le a_i \le 1000000$ 。