序列数

题目描述

给你一个序列 a = (a1, a2, a3, ..., an) 和一个整数 x，求满足下列条件的非空区间 [l, r] 的个数：

1. a[l] xor a[l+1] xor ... xor a[r] = x
2. (r - l + 1) % 2 = 0，即区间长度为偶数

其中 xor 表示按位异或运算。

输入格式

第一行输入一个整数 n，表示序列长度。

第二行输入 n 个整数，表示序列 a。

第三行输入一个整数 x。

输出格式

输出一个整数，表示满足条件的区间个数。

数据范围

1 <= n <= 10^5

1 <= a[i] <= 10^9

0 <= x <= 10^9

样例 1

输入

5
1 2 3 2 1
2

输出

2