如果一個非負整數集合 $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$,所以佢唔係異或排斥嘅。