问題描述

高橋君有 $N$ 条腿，第 $i$ 条腿是由 $L_i$ 根骨头依次连接而成的结构。每条腿的一端都连接到高橋君的躯干上，躯干上没有骨头。

这次，高橋君决定在自己所有腿的所有骨头上写入字符 $0$ 或 $1$。

高橋君非常追求字符的书写方式，他只满足于以下条件：对于任意不同的两条腿 $A, B$，从与 $A$ 的躯干相连的另一端开始，到与 $B$ 的躯干相连的另一端结束的路径上的所有骨头上的字符，按照顺序读取时是回文的。

请计算满足高橋君要求的字符书写方式的数量，并将其除以 $10^9+7$ 取余数。

输入

输入从标准输入读取，具体格式如下：

$N$

$L_1$

...

$L_N$

• 第1行包含一个整数 $N$（$1 \leq N \leq 100000$），表示高橋君的腿的数量。
• 接下来的 $N$ 行，每行包含一个整数 $L_i$（$1 \leq L_i \leq 10^9$），表示第 $i$ 条腿的长度。

输出

输出到标准输出，包含一个整数，表示满足高橋君要求的字符书写方式的数量除以 $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