Decimos que un conjunto $S$ de enteros no negativos es excluyente de XOR (XOR-excluding) si el XOR de todos los elementos en $S$ no pertenece al propio conjunto $S$.
Dado un conjunto $A$ inicialmente vacío, le añadimos $n$ elementos positivos distintos $a_i$ uno por uno. Después de cada adición, encuentra el número de subconjuntos excluyentes de XOR de $A$.
Como la respuesta puede ser muy grande, imprímela módulo $10^9 + 7$.
Entrada
La primera línea de la entrada contiene un solo entero $n$ — el número de elementos a añadir.
Las siguientes $n$ líneas contienen cada una un solo entero $a_i$ — el $i$-ésimo elemento a añadir al conjunto.
Salida
Imprime $n$ líneas. En la $i$-ésima línea, imprime el número de subconjuntos excluyentes de XOR de $A$ después de añadir los primeros $i$ elementos, módulo $10^9 + 7$.
Restricciones
- $1 \le n \le 2 \cdot 10^5$,
- $1 \le a_i \le 2^{60} - 1$,
- todos los $a_i$ son distintos.
Ejemplo 1
5
1
2
3
4
5
1
2
5
11
22
Notas
Después de añadir $1$, el único subconjunto excluyente de XOR es $\{\}$ (el conjunto vacío tiene XOR igual a $0$).
Después de añadir $2$, los subconjuntos excluyentes de XOR son $\{\}$ y $\{1, 2\}$ (que tiene XOR igual a $3$).
Después de añadir $3$, los subconjuntos excluyentes de XOR son $\{\}$, $\{1, 2\}$, $\{1, 3\}$, $\{2, 3\}$ y $\{1, 2, 3\}$.
Después de añadir $4$, los subconjuntos excluyentes de XOR son $\{\}$, $\{1, 2\}$, $\{1, 3\}$, $\{1, 4\}$, $\{2, 3\}$, $\{2, 4\}$, $\{3, 4\}$, $\{1, 2, 3\}$, $\{1, 2, 4\}$, $\{1, 3, 4\}$ y $\{2, 3, 4\}$. Nota que $\{1, 2, 3, 4\}$ tiene XOR igual a $3$, por lo que no es excluyente de XOR.