AT_arc048_c.[ARC048C] 足の多い高橋君

高桥君有 $N$ 条腿，第 $i$ 条腿由 $L_i$ 块骨头首尾相连组成。所有腿的一端都连接在高桥君的躯干上，而躯干本身没有骨头。

这次高桥君打算在自己所有腿的所有骨头上写上 $0$ 或 $1$ 这两个字符中的一个。

高桥君对写字符的方式有很强的执着：对于任意两条不同的腿 $A,B$，如果从 $A$ 的远离躯干的一端出发，经过躯干，再到 $B$ 的远离躯干的一端，沿途依次读取骨头上的字符，所得的字符串是回文串，则高桥君会感到满意，并且只有在这种情况下才会满意。

请你求出高桥君感到满意的写法有多少种，并将答案对 $10^9+7$ 取模后输出。

输入按以下格式从标准输入读入。

$N$
$L_1$
$L_2$
$\vdots$
$L_N$

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

输出一个整数，表示高桥君感到满意的写法数对 $10^9+7$ 取模的结果。

输出最后请不要忘记换行。

样例解释 1

对于 $3$ 条腿，从远离躯干的一端开始读取每条腿的字符串，例如 $(01,0111,01111111)$ 等都满足条件。

由 ChatGPT 4.1 翻译