Problem Statement

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

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

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

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

Input

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

N
L_1
.
.
.
L_N

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

Output

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

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