Question
Magical Array Partitioning
Aria was determined to find all the different ways she could partition her array into valid subarrays. Can you help her calculate the total number of valid partitions, ensuring the answer is given modulo 109 + 7?
In a whimsical land of numbers, Aria was tasked with organizing a colorful array of N magical creatures represented by the elements of array A. Each creature had its own unique traits, and Aria needed to ensure they were grouped properly. To do this, she decided to partition the array into several non-empty valid subarrays. A subarray could be deemed valid if it met at least one of the following criteria:
- The subarray contained just one creature.
- The XOR of the traits of the creatures within the subarray equaled a power of 2.
Aria was determined to find all the different ways she could partition her array into valid subarrays. Can you help her calculate the total number of valid partitions, ensuring the answer is given modulo 109 + 7?
Input
The first line of the input contains a single integer N, denoting the size of an array.
The second line of the input contains N space-separated integers, denoting the array A.
Constraints
1 ≤ N ≤ 105
1 ≤ Ai ≤ 106
The second line of the input contains N space-separated integers, denoting the array A.
Constraints
1 ≤ N ≤ 105
1 ≤ Ai ≤ 106
Output
Print the total number of ways to partition the arrays into non-empty valid subarrays so that the above conditions are satisified, modulo 109 + 7.
Example
Sample Input
4
1 2 3 4
Sample Output
3
Explanation
The following subarray distributions are valid:
[1], [2], [3], [4]
[1], [2, 3], [4]
[1, 2, 3, 4]
4
1 2 3 4
Sample Output
3
Explanation
The following subarray distributions are valid:
[1], [2], [3], [4]
[1], [2, 3], [4]
[1, 2, 3, 4]