Vi sier at en mengde $S$ av ikke-negative heltall er XOR-ekskluderende (XOR-excluding) hvis XOR av alle elementene i $S$ ikke ligger i selve mengden $S$.
Gitt en opprinnelig tom mengde $A$, legger vi til $n$ distinkte positive elementer $a_i$ i den ett etter ett. Etter hvert tillegg, finn antall XOR-ekskluderende delmengder av $A$.
Siden svaret kan være svært stort, skriv det ut modulo $10^9 + 7$.
Inndata
Den første linjen i inndataene inneholder et enkelt heltall $n$ — antall elementer som skal legges til.
De følgende $n$ linjene inneholder hver et enkelt heltall $a_i$ — det $i$-te elementet som skal legges til i mengden.
Utdata
Skriv ut $n$ linjer. På den $i$-te linjen skal du skrive ut antall XOR-ekskluderende delmengder av $A$ etter å ha lagt til de første $i$ elementene, modulo $10^9 + 7$.
Begrensninger
- $1 \le n \le 2 \cdot 10^5$,
- $1 \le a_i \le 2^{60} - 1$,
- alle $a_i$ er distinkte.
Eksempel 1
5
1
2
3
4
5
1
2
5
11
22
Merknader
Etter å ha lagt til $1$, er den eneste XOR-ekskluderende delmengden $\{\}$ (den tomme mengden har XOR lik $0$).
Etter å ha lagt til $2$, er de XOR-ekskluderende delmengdene $\{\}$ og $\{1, 2\}$ (som har XOR lik $3$).
Etter å ha lagt til $3$, er de XOR-ekskluderende delmengdene $\{\}$, $\{1, 2\}$, $\{1, 3\}$, $\{2, 3\}$ og $\{1, 2, 3\}$.
Etter å ha lagt til $4$, er de XOR-ekskluderende delmengdene $\{\}$, $\{1, 2\}$, $\{1, 3\}$, $\{1, 4\}$, $\{2, 3\}$, $\{2, 4\}$, $\{3, 4\}$, $\{1, 2, 3\}$, $\{1, 2, 4\}$, $\{1, 3, 4\}$ og $\{2, 3, 4\}$. Merk at $\{1, 2, 3, 4\}$ har XOR lik $3$, så den er ikke XOR-ekskluderende.