Sanomme, että epänegatiivisten kokonaislukujen joukko $S$ on XOR-poissulkeva (XOR-excluding), jos kaikkien joukon $S$ alkioiden XOR ei kuulu itse joukkoon $S$.
Annettuna on aluksi tyhjä joukko $A$, johon lisäämme $n$ erisuurta positiivista alkiota $a_i$ yksitellen. Etsi jokaisen lisäyksen jälkeen joukon $A$ XOR-poissulkevien osajoukkojen lukumäärä.
Koska vastaus voi olla hyvin suuri, tulosta se modulo $10^9 + 7$.
Syöte
Syötteen ensimmäinen rivi sisältää yhden kokonaisluvun $n$ — lisättävien alkioiden lukumäärän.
Seuraavat $n$ riviä sisältävät kukin yhden kokonaisluvun $a_i$ — joukkoon lisättävän $i$-nnen alkion.
Tuloste
Tulosta $n$ riviä. Tulosta $i$-nnelle riville joukon $A$ XOR-poissulkevien osajoukkojen lukumäärä ensimmäisen $i$ alkion lisäämisen jälkeen modulo $10^9 + 7$.
Rajoitukset
- $1 \le n \le 2 \cdot 10^5$,
- $1 \le a_i \le 2^{60} - 1$,
- kaikki $a_i$ ovat erisuuria.
Esimerkki 1
5
1
2
3
4
5
1
2
5
11
22
Huomautukset
Kun on lisätty $1$, ainoa XOR-poissulkeva osajoukko on $\{\}$ (tyhjän joukon XOR on $0$).
Kun on lisätty $2$, XOR-poissulkevat osajoukot ovat $\{\}$ ja $\{1, 2\}$ (jonka XOR on $3$).
Kun on lisätty $3$, XOR-poissulkevat osajoukot ovat $\{\}$, $\{1, 2\}$, $\{1, 3\}$, $\{2, 3\}$ ja $\{1, 2, 3\}$.
Kun on lisätty $4$, XOR-poissulkevat osajoukot ovat $\{\}$, $\{1, 2\}$, $\{1, 3\}$, $\{1, 4\}$, $\{2, 3\}$, $\{2, 4\}$, $\{3, 4\}$, $\{1, 2, 3\}$, $\{1, 2, 4\}$, $\{1, 3, 4\}$ ja $\{2, 3, 4\}$. Huomaa, että joukon $\{1, 2, 3, 4\}$ XOR on $3$, joten se ei ole XOR-poissulkeva.