题目描述

小火车沉迷于垃圾游戏不能自拔，他不光自己在玩碧蓝游戏，还决定把你也拉入坑！
你已经忍无可忍了，你决定出个难题把他按在地上摩擦！正巧你研究了斐波那契数列，也就是 f(0)=0,f(1)=1,否则f(i)=f(i-1)+f(i-2)的那个数列。于是你问小火车,我给你n个数ki,你知道f(ki)的最小公倍数吗？让你惊讶不解的是,小火车竟然一边干着手游一边报出巨大的数字！你怀疑他是瞎猜的，所以想知道他回答的到底对不对，不过这个时候你就只需要知道答案对1000000007取模的结果啦！

输入格式

第一行一个整数n。
第二行n个整数表示 ki。

输出格式

一行一个整数表示答案

样例

样例输入

1 3 9 6

样例输出

136

数据范围

对于20%的数据，ki≤50；
对于50%的数据，ki≤5000；
对于100%的数据，n≤50000,ki≤1000000。