Назвемо множину $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\}$. Зауважте, що $\{1, 2, 3, 4\}$ має XOR, рівний $3$, тому вона не є XOR-виключною.