問題文

高橋君には足が $N$ 本あり、$i$ 番目の足は $L_i$ 本の骨が一列につながった構造をしています。 すべての足の片方の端は、高橋君の胴体につながっています。高橋君の胴体には骨はありません。

今回高橋君は、自分のすべての足のすべての骨に $0$ または $1$ の文字を書き込むことにしました。

高橋君は文字の書き込み方に強いこだわりを持っており、任意の異なる $2$ 本の足 $A,B$ について、 $A$ の胴体につながっていないほうの端から $B$ の胴体につながっていないほうの端までの胴体を経由する経路上にある骨に書かれた文字をすべて順に読むと回文になっているとき、またその時のみ満足します。

高橋君が満足する文字の書き込み方の数を $10^9+7$ で割った余りを求めてください。

入力

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

$N$ $L_1$ . . . $L_N$

• $1$ 行目には、高橋君の足の本数を表す整数 $N(1 ≦ N ≦ 100000)$ が与えられる。
• 続く $N$ 行には、$i$ 番目の足の長さを表す整数 $L_i(1 ≦ L_i ≦ 10^9)$ が与えられる。

出力

高橋君が満足する文字の書き込み方の数を $10^9+7$ で割った余りを表す整数 $1$ つを出力せよ。

出力の最後には改行を忘れないこと。

入力例1

3
2
4
8

出力例1

8

$3$ 本の足に書く文字列を胴体に接続していないほうから読むと、例えば $(01,0111,01111111)$ などが条件を満たします。

入力例2

8
2
1
4
3
6
5
8
7

出力例2

4

入力例3

5
700000000
20000000
9000000
600000000
30000000

出力例3

861838989