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) | Output (stdout) |
|---|---|
| 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.
Submit a solution
| Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
|---|
| Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
|---|