题目描述

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

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

输出格式

一行一个整数表示答案。

样例

input

4
1 3 9 6

output

136

数据范围与提示

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