A6036. 「2017 山东二轮集训 Day1」第三题
编程题
省选/NOI-
知识点
题目描述
火车沉迷垃圾手游不能自拔，他不光自己在玩碧蓝航线，还决定把你拉入坑。
你已经忍无可忍了！你决定出个难题把他按在地上摩擦！正巧你研究了斐波那契数列，也就是 $ f(0) = 0, f(1) = 1 $，否则 $ f(i) = f(i - 1) + f(i - 2) $ 的那个数列，于是你问小火车「我给你 $ n $ 个数 $ k_i $，你知道 $ f(k_i) $ 的最小公倍数吗？」让你惊讶不已的是，小火车竟然一边肝着手游一边报出了巨大的数字！你怀疑他是瞎猜的，所以想知道他回答的到底对不对，不过这个时候你就只需要知道答案对 $ 1000000007 $ 取模的结果啦！
你已经忍无可忍了！你决定出个难题把他按在地上摩擦！正巧你研究了斐波那契数列，也就是 $ 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 $。
第二行 $ n $ 个正整数表示 $ k_i $。
输出格式
一行一个整数表示答案。
输入输出样例
输入 #1
4 1 3 9 6
输出 #1
136
说明/提示
对于 $ 20\% $ 的数据，$ k_i \leq 50 $；
对于 $ 50\% $ 的数据，$ k_i \leq 5000 $；
对于 $ 100\% $ 的数据，$ n \leq 50000, k_i \leq 1000000 $。
对于 $ 50\% $ 的数据，$ k_i \leq 5000 $；
对于 $ 100\% $ 的数据，$ n \leq 50000, k_i \leq 1000000 $。