Question
Strong XOR Subarrays
In the kingdom of Arthimore, there lives a young wizard who studies the mysterious magic of numbers. His spellbook contains an array of n magical stones, each stone inscribed with an integer.
The wizard has discovered a curious phenomenon:
Whenever he selects a contiguous sequence of stones (a subarray) and channels their combined energy using the bitwise XOR spell, sometimes the result glows with a rare, powerful energy — the energy of pure powers of 2 (like 1, 2, 4, 8, 16, …).
Your task is to help the wizard count:
How many such magical subarrays exist, where the total XOR of all chosen stones equals a power of 2?
Input
The first line contains a single integer KaTeX can only parse string typed expression — the number of magical stones.
The second line contains KaTeX can only parse string typed expression integers, representing the inscriptions on the stones: KaTeX can only parse string typed expression.
The second line contains KaTeX can only parse string typed expression integers, representing the inscriptions on the stones: KaTeX can only parse string typed expression.
Output
Print a single integer — the total number of subarrays whose XOR equals a power of 2.
Example
Input
5
3 2 1 6 7
Output
6
Explanation
Choosing stones [3, 2, 1, 6, 7] together → XOR = 1 → Power of 2.
Choosing stones [3, 2] together → XOR = 1 → Power of 2!
Choosing stones [2, 1, 6, 7] together → XOR = 1 → Power of 2.
Choosing stone [2] alone → XOR = 2 → Power of 2!
Choosing stone [1] alone → XOR = 1 → Power of 2!
Choosing stones [6, 7] together → XOR = 1 → Power of 2!
In total, the wizard finds 6 glowing subarrays.
5
3 2 1 6 7
Output
6
Explanation
Choosing stones [3, 2, 1, 6, 7] together → XOR = 1 → Power of 2.
Choosing stones [3, 2] together → XOR = 1 → Power of 2!
Choosing stones [2, 1, 6, 7] together → XOR = 1 → Power of 2.
Choosing stone [2] alone → XOR = 2 → Power of 2!
Choosing stone [1] alone → XOR = 1 → Power of 2!
Choosing stones [6, 7] together → XOR = 1 → Power of 2!
In total, the wizard finds 6 glowing subarrays.