Mówimy, że zbiór $S$ nieujemnych liczb całkowitych jest wykluczający XOR (XOR-excluding), jeśli wynik operacji XOR wszystkich elementów w $S$ nie należy do samego zbioru $S$.
Mając początkowo pusty zbiór $A$, dodajemy do niego po kolei $n$ parami różnych dodatnich elementów $a_i$. Po każdym dodaniu znajdź liczbę podzbiorów zbioru $A$ wykluczających XOR.
Ponieważ odpowiedź może być bardzo duża, wypisz ją modulo $10^9 + 7$.
Wejście
Pierwszy wiersz wejścia zawiera jedną liczbę całkowitą $n$ — liczbę elementów do dodania.
Kolejne $n$ wierszy zawiera po jednej liczbie całkowitej $a_i$ — $i$-ty element dodawany do zbioru.
Wyjście
Wypisz $n$ wierszy. W $i$-tym wierszu wypisz liczbę podzbiorów zbioru $A$ wykluczających XOR po dodaniu pierwszych $i$ elementów, modulo $10^9 + 7$.
Ograniczenia
- $1 \le n \le 2 \cdot 10^5$,
- $1 \le a_i \le 2^{60} - 1$,
- wszystkie $a_i$ są parami różne.
Przykład 1
5
1
2
3
4
5
1
2
5
11
22
Uwagi
Po dodaniu $1$ jedynym podzbiorem wykluczającym XOR jest $\{\}$ (zbiór pusty ma XOR równy $0$).
Po dodaniu $2$ podzbiorami wykluczającymi XOR są $\{\}$ oraz $\{1, 2\}$ (którego XOR wynosi $3$).
Po dodaniu $3$ podzbiorami wykluczającymi XOR są $\{\}$, $\{1, 2\}$, $\{1, 3\}$, $\{2, 3\}$ oraz $\{1, 2, 3\}$.
Po dodaniu $4$ podzbiorami wykluczającymi XOR są $\{\}$, $\{1, 2\}$, $\{1, 3\}$, $\{1, 4\}$, $\{2, 3\}$, $\{2, 4\}$, $\{3, 4\}$, $\{1, 2, 3\}$, $\{1, 2, 4\}$, $\{1, 3, 4\}$ oraz $\{2, 3, 4\}$. Zauważ, że $\{1, 2, 3, 4\}$ ma XOR równy $3$, więc nie jest wykluczający XOR.