On dit qu'un ensemble $S$ d'entiers naturels est excluant le XOR (XOR-excluding) si le XOR de tous les éléments de $S$ n'appartient pas à l'ensemble $S$ lui-même.
Soit un ensemble $A$ initialement vide, auquel on ajoute un par un $n$ éléments strictement positifs distincts $a_i$. Après chaque ajout, déterminez le nombre de sous-ensembles de $A$ qui excluent le XOR.
Comme la réponse peut être très grande, affichez-la modulo $10^9 + 7$.
Entrée
La première ligne de l'entrée contient un seul entier $n$ — le nombre d'éléments à ajouter.
Les $n$ lignes suivantes contiennent chacune un seul entier $a_i$ — le $i$-ème élément à ajouter à l'ensemble.
Sortie
Affichez $n$ lignes. Sur la $i$-ème ligne, affichez le nombre de sous-ensembles de $A$ excluant le XOR après l'ajout des $i$ premiers éléments, modulo $10^9 + 7$.
Contraintes
- $1 \le n \le 2 \cdot 10^5$,
- $1 \le a_i \le 2^{60} - 1$,
- tous les $a_i$ sont distincts.
Exemple 1
5
1
2
3
4
5
1
2
5
11
22
Notes
Après avoir ajouté $1$, le seul sous-ensemble excluant le XOR est $\{\}$ (l'ensemble vide a un XOR égal à $0$).
Après avoir ajouté $2$, les sous-ensembles excluant le XOR sont $\{\}$ et $\{1, 2\}$ (qui a un XOR égal à $3$).
Après avoir ajouté $3$, les sous-ensembles excluant le XOR sont $\{\}$, $\{1, 2\}$, $\{1, 3\}$, $\{2, 3\}$ et $\{1, 2, 3\}$.
Après avoir ajouté $4$, les sous-ensembles excluant le XOR sont $\{\}$, $\{1, 2\}$, $\{1, 3\}$, $\{1, 4\}$, $\{2, 3\}$, $\{2, 4\}$, $\{3, 4\}$, $\{1, 2, 3\}$, $\{1, 2, 4\}$, $\{1, 3, 4\}$ et $\{2, 3, 4\}$. Notez que $\{1, 2, 3, 4\}$ a un XOR égal à $3$, il n'exclut donc pas le XOR.