Kita menyebut suatu himpunan bilangan bulat non-negatif $S$ bersifat pengecuali-XOR (XOR-excluding) jika hasil XOR dari semua elemen di dalam $S$ tidak berada di dalam himpunan $S$ itu sendiri.
Diberikan suatu himpunan $A$ yang awalnya kosong, kita menambahkan $n$ elemen positif berbeda $a_i$ ke dalamnya satu per satu. Setelah setiap penambahan, carilah banyaknya himpunan bagian dari $A$ yang bersifat pengecuali-XOR.
Karena jawabannya bisa sangat besar, keluarkan hasilnya modulo $10^9 + 7$.
Masukan
Baris pertama masukan berisi sebuah bilangan bulat $n$ — banyaknya elemen yang akan ditambahkan.
$n$ baris berikutnya masing-masing berisi sebuah bilangan bulat $a_i$ — elemen ke-$i$ yang akan ditambahkan ke himpunan.
Keluaran
Cetak $n$ baris. Pada baris ke-$i$, cetak banyaknya himpunan bagian pengecuali-XOR dari $A$ setelah menambahkan $i$ elemen pertama, modulo $10^9 + 7$.
Batasan
- $1 \le n \le 2 \cdot 10^5$,
- $1 \le a_i \le 2^{60} - 1$,
- semua $a_i$ berbeda.
Contoh 1
5
1
2
3
4
5
1
2
5
11
22
Catatan
Setelah menambahkan $1$, satu-satunya himpunan bagian pengecuali-XOR adalah $\{\}$ (himpunan kosong memiliki nilai XOR sama dengan $0$).
Setelah menambahkan $2$, himpunan bagian pengecuali-XOR adalah $\{\}$ dan $\{1, 2\}$ (yang memiliki nilai XOR sama dengan $3$).
Setelah menambahkan $3$, himpunan bagian pengecuali-XOR adalah $\{\}$, $\{1, 2\}$, $\{1, 3\}$, $\{2, 3\}$, dan $\{1, 2, 3\}$.
Setelah menambahkan $4$, himpunan bagian pengecuali-XOR adalah $\{\}$, $\{1, 2\}$, $\{1, 3\}$, $\{1, 4\}$, $\{2, 3\}$, $\{2, 4\}$, $\{3, 4\}$, $\{1, 2, 3\}$, $\{1, 2, 4\}$, $\{1, 3, 4\}$, dan $\{2, 3, 4\}$. Perhatikan bahwa $\{1, 2, 3, 4\}$ memiliki nilai XOR sama dengan $3$, sehingga bukan merupakan pengecuali-XOR.