Wir nennen eine Menge $S$ nichtnegativer ganzer Zahlen XOR-ausschließend (XOR-excluding), wenn das XOR aller Elemente in $S$ nicht selbst in der Menge $S$ enthalten ist.
Gegeben ist eine anfangs leere Menge $A$, zu der wir nacheinander $n$ paarweise verschiedene positive Elemente $a_i$ hinzufügen. Bestimme nach jedem Hinzufügen die Anzahl der XOR-ausschließenden Teilmengen von $A$.
Da die Antwort sehr groß sein kann, gib sie modulo $10^9 + 7$ aus.
Eingabe
Die erste Zeile der Eingabe enthält eine einzelne ganze Zahl $n$ — die Anzahl der hinzuzufügenden Elemente.
Die folgenden $n$ Zeilen enthalten jeweils eine einzelne ganze Zahl $a_i$ — das $i$-te Element, das zur Menge hinzugefügt wird.
Ausgabe
Gib $n$ Zeilen aus. Gib in der $i$-ten Zeile die Anzahl der XOR-ausschließenden Teilmengen von $A$ nach dem Hinzufügen der ersten $i$ Elemente modulo $10^9 + 7$ aus.
Bedingungen
- $1 \le n \le 2 \cdot 10^5$,
- $1 \le a_i \le 2^{60} - 1$,
- alle $a_i$ sind paarweise verschieden.
Beispiel 1
5
1
2
3
4
5
1
2
5
11
22
Hinweise
Nach dem Hinzufügen von $1$ ist die einzige XOR-ausschließende Teilmenge $\{\}$ (die leere Menge hat ein XOR von $0$).
Nach dem Hinzufügen von $2$ sind die XOR-ausschließenden Teilmengen $\{\}$ und $\{1, 2\}$ (welche ein XOR von $3$ hat).
Nach dem Hinzufügen von $3$ sind die XOR-ausschließenden Teilmengen $\{\}$, $\{1, 2\}$, $\{1, 3\}$, $\{2, 3\}$ und $\{1, 2, 3\}$.
Nach dem Hinzufügen von $4$ sind die XOR-ausschließenden Teilmengen $\{\}$, $\{1, 2\}$, $\{1, 3\}$, $\{1, 4\}$, $\{2, 3\}$, $\{2, 4\}$, $\{3, 4\}$, $\{1, 2, 3\}$, $\{1, 2, 4\}$, $\{1, 3, 4\}$ und $\{2, 3, 4\}$. Beachte, dass $\{1, 2, 3, 4\}$ ein XOR von $3$ hat und daher nicht XOR-ausschließend ist.