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

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

3 секунди
512 мегабайтів
Дуже складна

Назвемо множину невід’ємних цілих чисел XOR-виключною, якщо результат побітової операції XOR над усіма її елементами не належить самій множині .

Спочатку задано порожню множину . До неї по черзі додають різних додатних елементів a_i. Після кожного додавання визначте кількість XOR-виключних підмножин множини .

Оскільки відповідь може бути дуже великою, виведіть її за модулем 10^9 + 7.

Вхідні дані

У першому рядку задано ціле число — кількість елементів, які буде додано.

У наступних рядках задано по одному цілому числу a_i — -й елемент, який додається до множини.

1 \le n \le 2 \cdot 10^5,

1 \le a_i \le 2^{60} - 1,

усі a_i різні.

Вихідні дані

Виведіть рядків. У -му рядку виведіть кількість XOR-виключних підмножин множини після додавання перших елементів за модулем 10^9 + 7.

Приклади

Приклад

Loading
Loading

Примітка

Після додавання числа єдиною XOR-виключною підмножиною є (порожня множина має XOR, що дорівнює ).

Після додавання числа XOR-виключними є підмножини та (її XOR дорівнює ).

Після додавання числа XOR-виключними є підмножини , , , та \{1,2,3\}.

Після додавання числа XOR-виключними є підмножини , , , , , , , \{1,2,3\}, \{1,2,4\}, \{1,3,4\} та \{2,3,4\}. Зауважте, що для множини \{1,2,3,4\} значення XOR дорівнює , тому вона не є XOR-виключною.