Problem Brief

XOR Coloring

See Microsoft online assessment and hiring insights

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 🍊

1Example 1

Input

A = [1, 2]

Output

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.

2Example 2

Input

A = [3, 5, 7]

Output

Explanation

Here, N=3 and A=[5, 3, 7] There isn't any good coloring in this sample. Hence, the answer is 0.

3Example 3

Input

A = [2, 3, 9]

Output

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.

Constraints

Limits and guarantees your solution can rely on.

1 ≤ N ≤ 10^5

1 ≤ A[i] ≤ 10^5