题目描述

给一个长度为$\red n$的数组 $\red{a_1,a_2,. . . ,a_n}$ ，

问有多少组满足条件的 $\red{ b_1, b_2, b_3, b_4(1 ≤ b_1 < b_2 < b_3 < b_4 ≤n )}$ 满足 $\red{a_{b1}xor a_{b2} xor a_{b3} xor a_{b4} = 0}$。

输入格式

第一行一个整数$\red n$ 表示数组长度。

接下来一行 $\red n$个整数，第$\red i$个整数 表示数组中第$\red i$个元素的值。

输出格式

输出一个数，表示答案。

输入样例

6
1 3 0 0 2 2

输出样例

5

输入输出样例2

请下载文件

样例解释

$\red {b= \{1,2,3,5\}, \{1,2,3,6\}, \{1,2,4,5\},\{1,2,4,6\}, \{3,4,5,6\} }$

提示：

数据规模 共 $\red {10}$组数据，

测试点 $\red{ 1,2}$满足，$\red { n≤ 100,a_i ≤ 1000}$。

测试点 $\red{3,4}$满足，$\red {n ≤ 1000,a_i ≤ 1000}$。

测试点 $\red{5,6}$满足，$\red {n ≤ 5000, a_i≤ 1000}$。

对于 $\red{100\%}$的数据，满足$\red { 4 ≤ n ≤ 5000,0 ≤ a_i ≤ 1000000。}$