Ta nói rằng một tập hợp $S$ gồm các số nguyên không âm là loại trừ XOR (XOR-excluding) nếu tổng XOR của tất cả các phần tử trong $S$ không nằm trong chính tập hợp $S$.
Cho một tập hợp $A$ ban đầu rỗng, ta lần lượt thêm $n$ phần tử nguyên dương phân biệt $a_i$ vào tập hợp từng phần tử một. Sau mỗi lần thêm, hãy tìm số lượng tập con loại trừ XOR của $A$.
Vì đáp án có thể rất lớn, hãy in ra kết quả theo modulo $10^9 + 7$.
Dữ liệu vào
Dòng đầu tiên của dữ liệu vào chứa một số nguyên duy nhất $n$ — số lượng phần tử cần thêm.
$n$ dòng tiếp theo, mỗi dòng chứa một số nguyên duy nhất $a_i$ — phần tử thứ $i$ được thêm vào tập hợp.
Dữ liệu ra
In ra $n$ dòng. Trên dòng thứ $i$, in ra số lượng tập con loại trừ XOR của $A$ sau khi thêm $i$ phần tử đầu tiên, theo modulo $10^9 + 7$.
Giới hạn
- $1 \le n \le 2 \cdot 10^5$,
- $1 \le a_i \le 2^{60} - 1$,
- tất cả các $a_i$ đều đôi một phân biệt.
Ví dụ 1
5
1
2
3
4
5
1
2
5
11
22
Ghi chú
Sau khi thêm $1$, tập con loại trừ XOR duy nhất là $\{\}$ (tập rỗng có tổng XOR bằng $0$).
Sau khi thêm $2$, các tập con loại trừ XOR là $\{\}$ và $\{1, 2\}$ (có tổng XOR bằng $3$).
Sau khi thêm $3$, các tập con loại trừ XOR là $\{\}$, $\{1, 2\}$, $\{1, 3\}$, $\{2, 3\}$ và $\{1, 2, 3\}$.
Sau khi thêm $4$, các tập con loại trừ XOR là $\{\}$, $\{1, 2\}$, $\{1, 3\}$, $\{1, 4\}$, $\{2, 3\}$, $\{2, 4\}$, $\{3, 4\}$, $\{1, 2, 3\}$, $\{1, 2, 4\}$, $\{1, 3, 4\}$ và $\{2, 3, 4\}$. Lưu ý rằng $\{1, 2, 3, 4\}$ có tổng XOR bằng $3$, nên nó không phải là tập loại trừ XOR.