如果一個非負整數集合 $S$ 中所有元素的互斥或和(XOR)不在集合 $S$ 本身之中,我們就稱集合 $S$ 是 異或排斥(XOR-excluding) 的。
給定一個初始為空的集合 $A$,我們依序將 $n$ 個互不相同的正整數元素 $a_i$ 逐一加入其中。每次加入後,請求出 $A$ 的異或排斥子集的數量。
由於答案可能非常大,請輸出答案對 $10^9 + 7$ 取模後的結果。
輸入格式
輸入的第一行包含一個整數 $n$ —— 要加入的元素數量。
接下來的 $n$ 行,每行包含一個整數 $a_i$ —— 要加入集合的第 $i$ 個元素。
輸出格式
輸出 $n$ 行。在第 $i$ 行,輸出加入前 $i$ 個元素後,$A$ 的異或排斥子集數量對 $10^9 + 7$ 取模後的結果。
數據範圍
- $1 \le n \le 2 \cdot 10^5$,
- $1 \le a_i \le 2^{60} - 1$,
- 所有 $a_i$ 互不相同。
範例 1
5
1
2
3
4
5
1
2
5
11
22
範例說明
加入 $1$ 之後,唯一的異或排斥子集是 $\{\}$(空集的互斥或和等於 $0$)。
加入 $2$ 之後,異或排斥子集有 $\{\}$ 和 $\{1, 2\}$(其互斥或和等於 $3$)。
加入 $3$ 之後,異或排斥子集有 $\{\}$、$\{1, 2\}$、$\{1, 3\}$、$\{2, 3\}$ 和 $\{1, 2, 3\}$。
加入 $4$ 之後,異或排斥子集有 $\{\}$、$\{1, 2\}$、$\{1, 3\}$、$\{1, 4\}$、$\{2, 3\}$、$\{2, 4\}$、$\{3, 4\}$、$\{1, 2, 3\}$、$\{1, 2, 4\}$、$\{1, 3, 4\}$ 和 $\{2, 3, 4\}$。注意 $\{1, 2, 3, 4\}$ 的互斥或和等於 $3$,因此它不是異或排斥的。