题目描述

小$\red{H}$是个善于思考的学生，她正在思考一个有关序列的问题。

她的面前浮现出了一个长度为$\red{n}$的序列$\red{{ai}，}$她想找出两个非空的集合$\red{S}$、$\red{T}$。 这两个集合要满足以下的条件：

$\red{1. }$两个集合中的元素都为整数，且都在 $\red{[1, n] }$里，即$\red{Si，}$$\red{Ti ∈}$ $\red{[1, n]}$。

$\red{2. }$对于集合$\red{S}$中任意一个元素$\red{x，}$集合$\red{T}$中任意一个元素$\red{y，}$满足$\red{x < y}$。

$\red{3. }$对于大小分别为$\red{p, q}$的集合$\red{S}$与$\red{T，}$满足 $\red{a[s1] xor a[s2] xor a[s3] ... xor a[sp] = a[t1] and a[t2] and a[t3] ... and a[tq].}$

小$\red{H}$想知道一共有多少对这样的集合$\red{(S,T)，}$你能帮助她吗？

输入格式

第一行，一个整数$\red{n}$

第二行，$\red{n}$个整数，代表$\red{ai}$。

输出格式

仅一行，表示最后的答案。

样例

输入样例

4 
1 2 3 3

输出样例

4

提示

样例解释 $\red{S = \{1,2\}, T = \{3\}，}$ $\red{~~1 \Lambda 2 = 3 = 3 (\Lambda}$为异或$\red{)}$

$\red{S = \{1,2\}, T = \{4\}, ~~1 \Lambda 2 = 3 = 3}$

$\red{S = \{1,2\}，}$ $\red{T = \{3，}$$\red{4\} ~~ 1 \Lambda 2 = 3 \& 3 = 3 （}$$\red{\&}$为与运算）

$\red{S = \{3\}，}$ $\red{T = \{4\} ~~ 3 = 3 = 3 }$

数据范围 $\red{30\%: 1 <= n <= 10}$

$\red{60\%: 1 <= n <= 100}$

$\red{100\%: 1 <= n <= 1000, 0 <= ai < 1024}$