非負整数の集合 $S$ について、$S$ のすべての要素の排他的論理和(XOR)が集合 $S$ 自身に含まれないとき、その集合を XOR排他的(XOR-excluding) であると呼びます。
最初は空である集合 $A$ に対し、$n$ 個の相異なる正の要素 $a_i$ を1つずつ追加していきます。各追加の後に、$A$ の XOR排他的な部分集合の個数を求めてください。
答えは非常に大きくなる可能性があるため、$10^9 + 7$ で割った余りを出力してください。
入力
入力の1行目には、追加する要素の個数を表す単一の整数 $n$ が与えられます。
続く $n$ 行にはそれぞれ、集合に追加する $i$ 番目の要素を表す単一の整数 $a_i$ が与えられます。
出力
$n$ 行出力してください。$i$ 行目には、最初の $i$ 個の要素を追加した後の $A$ の XOR排他的な部分集合の個数を $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$ を追加した後、唯一の XOR排他的な部分集合は $\{\}$ です(空集合の XOR は $0$ に等しいです)。
$2$ を追加した後、XOR排他的な部分集合は $\{\}$ と $\{1, 2\}$(その XOR は $3$ に等しい)です。
$3$ を追加した後、XOR排他的な部分集合は $\{\}$, $\{1, 2\}$, $\{1, 3\}$, $\{2, 3\}$, $\{1, 2, 3\}$ です。
$4$ を追加した後、XOR排他的な部分集合は $\{\}$, $\{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\}$ の XOR は $3$ に等しいため、XOR排他的ではないことに注意してください。