You are given an array A consisting of n integers. You must split it into exactly three non-empty, contiguous, and non-overlapping parts.
Formally, you need to choose two indices
i and
j (
1 \le i < j < n) to divide the array into:
Part 1: A_1, A_2, \dots, A_i
Part 2: A_{i+1}, A_{i+2}, \dots, A_j
Part 3: A_{j+1}, A_{j+2}, \dots, A_n
Find the number of pairs
(i, j) such that the bitwise XOR sum of the elements in each part is equal:
XOR(A_1, \dots, A_i) = XOR(A_{i+1}, \dots, A_j) = XOR(A_{j+1}, \dots, A_n)
Input
The first line contains an integer n (3 \le n \le 10^6), the size of the array.
The second line contains n space-separated integers A_k (1 \le A_k \le 10^9).
Output
Print the total number of ways to split the array into three parts with equal XOR sums.
Examples
| standard input | standard output |
|---|
| 3
2 2 2
| 1
|
| 3
2 3 4
| 0
|