Question
The Wizard’s Even-Powered Subsequences
In the kingdom of Bitland, the royal wizard loves playing with magical numbers. One day, he lined up KaTeX can only parse string typed expression magical stones, each engraved with a number.
The wizard defines a magical sequence as any non-empty subsequence of these stones. A subsequence can be formed by removing zero or more stones without changing the order of the remaining stones.
A sequence is considered even-powered if the bitwise XOR of all its numbers is even.
Your task is to help the wizard determine how many non-empty subsequences of the given stones are even-powered. Since the number of such subsequences can be very large, print the answer modulo KaTeX can only parse string typed expression.
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 — KaTeX can only parse string typed expression — the numbers engraved on the stones.
The second line contains KaTeX can only parse string typed expression integers — KaTeX can only parse string typed expression — the numbers engraved on the stones.
Output
Print a single integer — the number of non-empty subsequences whose bitwise XOR is even, modulo KaTeX can only parse string typed expression.
Example
Input
3
1 2 3
Output
3
Explanation
All possible non-empty subsequences are examined.
Subsequences with even XOR power are:
(2) → XOR = 2
(1, 3) → 1 ⊕ 3 = 2
(1, 2, 3) → 1 ⊕ 2 ⊕ 3 = 0
Total = 3 even-powered subsequences.
3
1 2 3
Output
3
Explanation
All possible non-empty subsequences are examined.
Subsequences with even XOR power are:
(2) → XOR = 2
(1, 3) → 1 ⊕ 3 = 2
(1, 2, 3) → 1 ⊕ 2 ⊕ 3 = 0
Total = 3 even-powered subsequences.