Назвемо множину невід’ємних цілих чисел 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.
Приклад
Після додавання числа єдиною 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-виключною.