Vi säger att en mängd $S$ av icke-negativa heltal är XOR-exkluderande (XOR-excluding) om XOR av alla element i $S$ inte ligger i själva mängden $S$.
Givet en från början tom mängd $A$, lägger vi till $n$ distinkta positiva element $a_i$ till den ett i taget. Efter varje tillägg, bestäm antalet XOR-exkluderande delmängder av $A$.
Eftersom svaret kan vara mycket stort, skriv ut det modulo $10^9 + 7$.
Indata
Den första raden i indatan innehåller ett enda heltal $n$ — antalet element som ska läggas till.
De följande $n$ raderna innehåller var och en ett enda heltal $a_i$ — det $i$-te elementet som ska läggas till i mängden.
Utdata
Skriv ut $n$ rader. På den $i$-te raden, skriv ut antalet XOR-exkluderande delmängder av $A$ efter att de första $i$ elementen har lagts till, modulo $10^9 + 7$.
Begränsningar
- $1 \le n \le 2 \cdot 10^5$,
- $1 \le a_i \le 2^{60} - 1$,
- alla $a_i$ är distinkta.
Exempel 1
5
1
2
3
4
5
1
2
5
11
22
Anmärkningar
Efter att ha lagt till $1$ är den enda XOR-exkluderande delmängden $\{\}$ (den tomma mängden har XOR lika med $0$).
Efter att ha lagt till $2$ är de XOR-exkluderande delmängderna $\{\}$ och $\{1, 2\}$ (som har XOR lika med $3$).
Efter att ha lagt till $3$ är de XOR-exkluderande delmängderna $\{\}$, $\{1, 2\}$, $\{1, 3\}$, $\{2, 3\}$ och $\{1, 2, 3\}$.
Efter att ha lagt till $4$ är de XOR-exkluderande delmängderna $\{\}$, $\{1, 2\}$, $\{1, 3\}$, $\{1, 4\}$, $\{2, 3\}$, $\{2, 4\}$, $\{3, 4\}$, $\{1, 2, 3\}$, $\{1, 2, 4\}$, $\{1, 3, 4\}$ och $\{2, 3, 4\}$. Notera att $\{1, 2, 3, 4\}$ har XOR lika med $3$, så den är inte XOR-exkluderande.