XOR-Excluding Sets#13010

XOR-Excluding Sets

3 seconds
512 megabytes
Very hard

We say that a set of non-negative integers is XOR-excluding if the XOR of all elements in is not in the set itself.

Given an initially empty set , we add distinct positive elements a_i to it one by one. After each addition, find the number of XOR-excluding subsets of .

Since the answer can be very large, output it modulo 10^9 + 7.

Input

The first line of the input contains a single integer – the number of elements to add.

The following lines each contain a single integer a_i – the -th element to add to the set.

1 \le n \le 2 \cdot 10^5,

1 \le a_i \le 2^{60} - 1,

all a_i are distinct.

Output

Print lines. On the -th line, print the number of XOR-excluding subsets of after adding the first elements, modulo 10^9 + 7.

Examples

Example

Loading
Loading

Note

After adding , the only XOR-excluding subset is (the empty set has XOR equal to ).

After adding , the XOR-excluding subsets are and (which has XOR equal to ).

After adding , the XOR-excluding subsets are , , , and \{1,2,3\}.

After adding , the XOR-excluding subsets are , , , , , , , \{1,2,3\}, \{1,2,4\}, \{1,3,4\} and \{2,3,4\}. Note that \{1,2,3,4\} has XOR equal to 4, so it is not XOR-excluding.