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.
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.
Print lines. On the -th line, print the number of XOR-excluding subsets of after adding the first elements, modulo 10^9 + 7.
Example
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.