题目描述

小 Z 有一个长度为 $n$ 的数组 $a_1,a_2,\cdots,a_n$，现在小 Z 想知道有多少个满足条件的四元组 $(i,j,k,l)$，满足 $1\le i < j < k < l \le n$，同时 $a_i \oplus a_j \oplus a_k \oplus a_l =0$。

其中 $\oplus$ 表示异或运算，在 C++ 中用 ^ 运算符表示。

输入格式

从 xor.in 文件读入数据。

第一行输入一个整数 $n$ 表示数组长度。

接下来一行有 $n$ 个整数，分别为 $a_1,a_2,\cdots,a_n$。

输出格式

输出到 xor.out 文件。

输出一行一个整数表示满足条件的四元组个数。

样例

6
1 3 0 0 2 2

5

样例2

点击链接 ex_xor2.in 和 ex_xor2.out 下载大样例 2 的输入数据和输出数据。

说明/提示

样例 1 解释

满足条件的四元组分别为 $(1,2,3,5),(1,2,3,6),(1,2,4,5),(1,2,4,6),(3,4,5,6)$。

数据范围

共 $10$ 组数据，具体分布如下：

测试点 $1-2$ 满足，$n\le 100,a_i\le 1000$。

测试点 $3-4$ 满足，$n\le 1000,a_i \le 1000$。

测试点 $5-6$ 满足，$n\le 5000,a_i\le 1000$。

对于 $100\%$ 的数据，满足 $4\le n \le 5000,0\le a_i\le 10^6$。