問題文

みそ君は，$N$ 個の部分からなる横に細長い1本のチョコレートをもらいました。
チョコレートのそれぞれの部分の固さは，$A_i$ $(1≤i≤N)$ で表されます。
また，チョコレートのそれぞれの部分の境目には切れ込みが入っています。
みそ君は，このチョコレートをある特殊な機械に入れ，いくつかの塊に分割しようと思いました。

その特殊な機械では，どの切れ込みに対しても $\frac{1}{2}$ の確率で，その切れ込みでチョコレートを分割するように動作します。

そうして，いくつかの塊に分割されたチョコレートの美味しさを次のように定義します。

• 美味しさは，各塊に含まれる部分の固さの $XOR$ をとった値の総和 である。

例として，$A_1 = 3$ , $A_2 = 1$ , $A_3 = 4$ であるチョコレートを，$(A_1,A_2),(A_3)$ に分割したとすると，$(A_1 \,XOR\, A_2 = 2),(A_3 = 4)$ となり，この分割の仕方での美味しさは $4+2=6$ となります。

最終的に得られる美味しさの期待値（これは有理数になります。）を，注記で述べるように $mod \; 1000000007$ で求めてください。

注記

有理数を出力する際は、まずその有理数を分数 $\frac{y}{x}$ で表してください。
ここで，$x,y$ は整数であり，$x$ は $1000000007$ で割り切れてはいけません。
そして，$xz ≡ y \; (mod \; 1000000007)$ となる $0$ 以上 $1000000006$ 以下の整数 $z$ を出力してください。

制約

$1≤N≤1000$
$0≤A_i≤10^9$

入力

出力

最終的に得られる美味しさの期待値を1行に出力してください。

入力例 1

3
3 1 4

出力例 1

7

分割の仕方は，$(3),(1),(4)$ と $(3,1),(4)$ と $(3),(1,4)$ と $(3,1,4)$ の $4$ 通りあり，それぞれの美味しさは $8,6,8,6$ です。よって，求める期待値は $7$ となります。

入力例 2

3
9 9 7

出力例 2

500000019

求める期待値は $15.4$ となりますが，出力すべき値は，$4*y≡62 \; (mod \; 1000000007)$ を満たす整数 $y$ で，この値は $500000019$ となります。