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

传统 1000 ms 512 MiB

$130$ 通过 $182$ 提交

题目描述

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

你已经忍无可忍了！你决定出个难题把他按在地上摩擦！正巧你研究了斐波那契数列，也就是 $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$。