問題文

Xl,r=1(l=0r=0),Xl1,rXl,r1otherwiseX_{l,r}=1 \quad (l=0\lor r=0),\quad X_{l-1,r} \oplus X_{l,r-1} \quad otherwise

Xl,rX_{l,r} を (l0,r0l \geq 0, r \geq 0) で定義します。

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

00=0,01=1,10=1,11=00 \oplus 0 = 0,\quad 0 \oplus 1 = 1,\quad 1 \oplus 0 = 1,\quad 1 \oplus 1 = 0

です。

長さ NN の配列 AA が与えられるので

i=0kAiXi,ki\sum_{i=0}^{k} A_i X_{i,k-i}

0k<N0 \leq k < N について mod 109+710^9 + 7 で求めてください。

制約

  • 1N2×1051 \leq N \leq 2 \times 10^5
  • 1Ai109,(0i<N)1 \leq A_i \leq 10^9,\quad(0 \leq i < N)

入力

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

NN
A1A_1 A2A_2 \dots ANA_N

出力

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

入力例 1

4
2 1 3 4

出力例 1

2
3
5
10

入力例 2

2
877914575 602436426

出力例 2

877914575
480350994

Submit


Go (1.21)