問題文

と $X_{l,r}$ を ($l \geq 0, r \geq 0$) で定義します。

ただし、$\oplus$ は xor である、つまり

です。

長さ $N$ の配列 $A$ が与えられるので

を $0 \leq k < N$ について mod $10^9 + 7$ で求めてください。

制約

• $1 \leq N \leq 2 \times 10^5$
• $1 \leq A_i \leq 10^9,\quad(0 \leq i < N)$

入力

入力は以下の形式で標準入力から与えられます。

出力

答えを $N$ 行で出力してください。 $i$ 行目に $k=i-1$ のときの計算結果を出力してください。

入力例 1

4
2 1 3 4

出力例 1

2
3
5
10

入力例 2

2
877914575 602436426

出力例 2

877914575
480350994