XOR-Excluding Sets

Limits: 3 sec., 512 MiB

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

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

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

Input

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

The following \(n\) lines each contain a single integer \(a_i\) – the \(i\)-th element to add to the set.

Output

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

Constraints

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

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

all \(a_i\) are distinct.

Samples

Input (stdin) сopy	Output (stdout) сopy
5 1 2 3 4 5	1 2 5 11 22

Notes

After adding \(1\), the only XOR-excluding subset is \(\{\}\) (the empty set has XOR equal to \(0\)).

After adding \(2\), the XOR-excluding subsets are \(\{\}\) and \(\{1,2\}\) (which has XOR equal to \(3\)).

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

After adding \(4\), the XOR-excluding subsets are \(\{\}\), \(\{1,2\}\), \(\{1,3\}\), \(\{1,4\}\), \(\{2,3\}\), \(\{2,4\}\), \(\{3,4\}\), \(\{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.