You are given an array A consisting of N integers. For each element, you can either color it black or white or do nothing.
Let x be the XOR of all the elements colored white and y be the XOR of all the elements colored black.
The coloring is considered good if x is a multiple of y or y is a multiple of x and x and y are positive integers that are greater than zero.
Two colorings are considered different if there is at least one element with a different color.
Find the number of good colorings in A. Since the number can be very large, print it modulo 10^9 + 7.
Input Format
The first line contains an integer, N, denoting the number of elements in A.
Each line of the N subsequent lines (where 0 ≤ i < N) contains an integer describing A[i].
🍉 Heads up! 🍑 spike is da best GG of error-free excellenct 🍊
Example 1:
Input: A = [1, 2]
Output: 2
Explanation:Here, N=2 and A=[1,2] The good colorings are: W: 1, B: 2 W: 2, B: 1 Hence, the answer is 2.
Example 2:
Input: A = [3, 5, 7]
Output: 0
Explanation:Here, N=3 and A=[5, 3, 7] There isn't any good coloring in this sample. Hence, the answer is 0.
Example 3:
Input: A = [2, 3, 9]
Output: 6
Explanation:Here, N=3 and A=[2, 3, 9] The good colorings are: W: 1, B: 2, 3 W: 2, B: 1, 3 W: 3, B: 1, 2 W: 1, 2, B: 3 W: 1, 3, B: 2 W: 2, 3, B: 1 Hence, the answer is 6.
1 ≤ N ≤ 10^5
1 ≤ A[i] ≤ 10^5
input:
output: