XOR-виключні множини

Обмеження: 3 сек., 512 МіБ

Назвемо множину \(S\) невід’ємних цілих чисел XOR-виключною, якщо результат побітової операції XOR над усіма її елементами не належить самій множині \(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\) різні.

Приклади

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
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 дорівнює \(4\), тому вона не є XOR-виключною.