Назовём множество $S$ неотрицательных целых чисел XOR-исключающим, если побитовое исключающее ИЛИ (XOR) всех элементов в $S$ не принадлежит самому множеству $S$.
Дано изначально пустое множество $A$, в которое по одному добавляют $n$ различных положительных элементов $a_i$. После каждого добавления найдите количество XOR-исключающих подмножеств множества $A$.
Так как ответ может быть очень большим, выведите его по модулю $10^9 + 7$.
Входные данные
Первая строка входных данных содержит одно целое число $n$ — количество добавляемых элементов.
Следующие $n$ строк содержат по одному целому числу $a_i$ — $i$-й элемент, добавляемый в множество.
Выходные данные
Выведите $n$ строк. В $i$-й строке выведите количество XOR-исключающих подмножеств множества $A$ после добавления первых $i$ элементов по модулю $10^9 + 7$.
Ограничения
- $1 \le n \le 2 \cdot 10^5$,
- $1 \le a_i \le 2^{60} - 1$,
- все $a_i$ различны.
Пример 1
5
1
2
3
4
5
1
2
5
11
22
Примечания
После добавления $1$ единственным XOR-исключающим подмножеством является $\{\}$ (пустое множество имеет XOR, равный $0$).
После добавления $2$ XOR-исключающими подмножествами являются $\{\}$ и $\{1, 2\}$ (XOR которого равен $3$).
После добавления $3$ XOR-исключающими подмножествами являются $\{\}$, $\{1, 2\}$, $\{1, 3\}$, $\{2, 3\}$ и $\{1, 2, 3\}$.
После добавления $4$ XOR-исключающими подмножествами являются $\{\}$, $\{1, 2\}$, $\{1, 3\}$, $\{1, 4\}$, $\{2, 3\}$, $\{2, 4\}$, $\{3, 4\}$, $\{1, 2, 3\}$, $\{1, 2, 4\}$, $\{1, 3, 4\}$ и $\{2, 3, 4\}$. Обратите внимание, что XOR множества $\{1, 2, 3, 4\}$ равен $3$, поэтому оно не является XOR-исключающим.