题目描述

小可可在五年级暑假开始学习编程，编程语言中有一种“按位异或(xor)”的运算引起了他的莫大兴趣。于是，他思考这样的一个问题：给一个长度为 $n$ 的整数序列 $A$，如何计算出满足下列两个条件的整数对 $(l,r)$ 的数量。

• 1.$1 \leq l \leq r \leq n$；
• 2.$A_l \oplus A_{l+1} \oplus \dots \oplus A_r = A_l + A_{l+1} + \dots + A_r$。

这里的 $\oplus$ 就是按位异或（C 或 C++语言中“按位异或”运算符为 ^），求 $a \oplus b$ 的原理是：将 $a$ 和 $b$ 转换为二进制，如果 $a$、$b$ 的二进制表示中对应位置不相同，则异或结果的二进制表示中对应位置为 1，如果 $a$、$b$ 的二进制表示中对应位置相同，则异或结果的二进制表示中对应位置为 0。例如：计算 $10 \oplus 12$，二进制表示 $10$ 是 $1010$，二进制表示 $12$ 是 $1100$，$10 \oplus 12$ 结果的二进制表示是 $0110$，即为 $6$。具体如下式(C++中异或为^)

小可可虽然提出了问题，但他自己不会解决，只好又要麻烦你解决啦。

输入格式

输入有两行：
第一行一个正整数 $n$，表示整数序列 $A$ 的元素个数。
第二行有 $n$ 个整数，第 $i$ 个整数 $A_i$ 表示整数序列 $A$ 的第 $i$ 个元素的值。

输出格式

输出一行，包括一个正整数，表示满足条件的整数对 $(l,r)$ 的数量。

样例

输入#1

4  
2 5 4 6  

输出#1

5  

解释#1

【样例 1 解释】
$(l,r) = (1,1)$、$(2,2)$、$(3,3)$、$(4,4)$ 显然满足条件，还有 $(l,r) = (1,2)$ 也满足条件，因为
$A_1 \oplus A_2 = 2 \oplus 5 = 7$，而
$A_1 + A_2 = 2 + 5 = 7$。
所以满足条件的整数对 $(l,r)$ 的数量为 5。

输入#2

19  
885 8 1 128 83 32 256 206 639 16 4 128 689 32 8 64 885 969 1  

输出#2

37  

数据范围

对于 $20\%$ 的数据满足：$A_i = 0 \ (1 \leq i \leq n)$。
另有 $30\%$ 的数据满足：$1 \leq n \leq 5000$。
对于 $100\%$ 的数据满足：$1 \leq n \leq 200000$，$0 \leq A_i \leq 2^{20}$。