問題文

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

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

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

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

入力例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