XOR-Excluding Sets
Обмеження: 3 сек., 512 МіБ
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\).
Вхідні дані
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.
Вихідні дані
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\).
Обмеження
\(1 \le n \le 2 \cdot 10^5\),
\(1 \le a_i \le 2^{60} - 1\),
all \(a_i\) are distinct.
Приклади
| Вхідні дані (stdin) | Вихідні дані (stdout) |
|---|---|
| 5 1 2 3 4 5 | 1 2 5 11 22 |
Примітки
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.
Надіслати розв'язок
| Element Type | Створено | Хто | Задача | Компілятор | Результат | Час (сек.) | Пам'ять (МіБ) | № | Дії |
|---|
| Element Type | Створено | Хто | Задача | Компілятор | Результат | Час (сек.) | Пам'ять (МіБ) | № | Дії |
|---|