Við segjum að mengi $S$ af óneikvæðum heiltölum sé XOR-útilokandi (XOR-excluding) ef XOR allra staka í $S$ er ekki í menginu $S$ sjálfu.
Gefið er í upphafi tómt mengi $A$ og við bætum $n$ ólíkum jákvæðum stökum $a_i$ við það einu í einu. Eftir hverja viðbót skal finna fjölda XOR-útilokandi hlutmengja í $A$.
Þar sem svarið getur verið mjög stórt skal prenta það modulo $10^9 + 7$.
Inntak
Fyrsta línan í inntakinu inniheldur eina heiltölu $n$ — fjölda staka sem á að bæta við.
Næstu $n$ línur innihalda hver um sig eina heiltölu $a_i$ — $i$-ta stakið sem bætt er við mengið.
Úttak
Prentið $n$ línur. Á $i$-tu línu skal prenta fjölda XOR-útilokandi hlutmengja í $A$ eftir að fyrstu $i$ stökunum hefur verið bætt við, modulo $10^9 + 7$.
Takmarkanir
- $1 \le n \le 2 \cdot 10^5$,
- $1 \le a_i \le 2^{60} - 1$,
- öll $a_i$ eru ólík.
Dæmi 1
5
1
2
3
4
5
1
2
5
11
22
Athugasemdir
Eftir að $1$ er bætt við er eina XOR-útilokandi hlutmengið $\{\}$ (tóma mengið hefur XOR jafnt og $0$).
Eftir að $2$ er bætt við eru XOR-útilokandi hlutmengin $\{\}$ og $\{1, 2\}$ (sem hefur XOR jafnt og $3$).
Eftir að $3$ er bætt við eru XOR-útilokandi hlutmengin $\{\}$, $\{1, 2\}$, $\{1, 3\}$, $\{2, 3\}$ og $\{1, 2, 3\}$.
Eftir að $4$ er bætt við eru XOR-útilokandi hlutmengin $\{\}$, $\{1, 2\}$, $\{1, 3\}$, $\{1, 4\}$, $\{2, 3\}$, $\{2, 4\}$, $\{3, 4\}$, $\{1, 2, 3\}$, $\{1, 2, 4\}$, $\{1, 3, 4\}$ og $\{2, 3, 4\}$. Athugið að $\{1, 2, 3, 4\}$ hefur XOR jafnt og $3$, svo það er ekki XOR-útilokandi.