#6102. 「2017 山东二轮集训 Day1」第三题

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

火车沉迷垃圾手游不能自拔,他不光自己在玩碧蓝航线,还决定把你拉入坑。

你已经忍无可忍了!你决定出个难题把他按在地上摩擦!正巧你研究了斐波那契数列,也就是 f(0) = 0, f(1) = 1 ,否则 f(i) = f(i - 1) + f(i - 2) 的那个数列,于是你问小火车「我给你 n 个数 k_i ,你知道 f(k_i) 的最小公倍数吗?」让你惊讶不已的是,小火车竟然一边肝着手游一边报出了巨大的数字!你怀疑他是瞎猜的,所以想知道他回答的到底对不对,不过这个时候你就只需要知道答案对 1000000007 取模的结果啦!

输入格式

第一行一个整数 n
第二行 n 个整数表示 k_i

输出格式

一行一个整数表示答案。

样例

样例输入

4
1 3 9 6

样例输出

136

数据范围与提示

对于 20\% 的数据, k_i \leq 50
对于 50\% 的数据, k_i \leq 5000
对于 100\% 的数据, n \leq 50000, k_i \leq 1000000