← 返回题目列表

AtCoder · arc048_c

C. 高桥有很多腿

中文机器翻译题面 查看原题

問題文

高桥有腿。 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