Diciamo che un insieme $S$ di interi non negativi è XOR-escludente (XOR-excluding) se lo XOR di tutti gli elementi in $S$ non appartiene all'insieme $S$ stesso.
Dato un insieme $A$ inizialmente vuoto, vi aggiungiamo $n$ elementi positivi distinti $a_i$ uno alla volta. Dopo ogni aggiunta, trova il numero di sottoinsiemi XOR-escludenti di $A$.
Poiché la risposta può essere molto grande, stampala modulo $10^9 + 7$.
Input
La prima riga dell'input contiene un singolo intero $n$ — il numero di elementi da aggiungere.
Le successive $n$ righe contengono ciascuna un singolo intero $a_i$ — l'$i$-esimo elemento da aggiungere all'insieme.
Output
Stampa $n$ righe. Sulla $i$-esima riga, stampa il numero di sottoinsiemi XOR-escludenti di $A$ dopo aver aggiunto i primi $i$ elementi, modulo $10^9 + 7$.
Vincoli
- $1 \le n \le 2 \cdot 10^5$,
- $1 \le a_i \le 2^{60} - 1$,
- tutti gli $a_i$ sono distinti.
Esempio 1
5
1
2
3
4
5
1
2
5
11
22
Note
Dopo aver aggiunto $1$, l'unico sottoinsieme XOR-escludente è $\{\}$ (l'insieme vuoto ha XOR uguale a $0$).
Dopo aver aggiunto $2$, i sottoinsiemi XOR-escludenti sono $\{\}$ e $\{1, 2\}$ (che ha XOR uguale a $3$).
Dopo aver aggiunto $3$, i sottoinsiemi XOR-escludenti sono $\{\}$, $\{1, 2\}$, $\{1, 3\}$, $\{2, 3\}$ e $\{1, 2, 3\}$.
Dopo aver aggiunto $4$, i sottoinsiemi XOR-escludenti sono $\{\}$, $\{1, 2\}$, $\{1, 3\}$, $\{1, 4\}$, $\{2, 3\}$, $\{2, 4\}$, $\{3, 4\}$, $\{1, 2, 3\}$, $\{1, 2, 4\}$, $\{1, 3, 4\}$ e $\{2, 3, 4\}$. Nota che $\{1, 2, 3, 4\}$ ha XOR uguale a $3$, quindi non è XOR-escludente.