You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

WMC 叕叕叕在玩 dinosaur !!!

题目描述

有一天，邪恶的 WMC 把小恐龙抓到了小恐龙战斗场。

小恐龙发现有 $n$ 个恐龙（不包括它自己），现在 WMC 每天会选两个小恐龙战斗，若其中一只恐龙的战斗力为 $x$，另一只恐龙的战斗力为 $y$, 则战斗力小的会牺牲，战斗力高的恐龙的战斗力会变为 $\gcd(x,y)$。

后来，WMC 发现了恐龙战斗力的秘密，第 $i$ 只小恐龙的战斗力为 $\text{fib}(a_i)$，又让小恐龙（小恐龙的战斗力为小于等于 $\text{fib}(10^7)$ 的正整数）与剩下的恐龙战斗，小恐龙活了下来，它想问你，它的战斗力最后最大值是多少？答案对 $10^9+7$ 取模。

输入格式

第 $1$ 行 $1$ 个整数 $n$.

第 $2$ 行 $n$ 个整数 $a_i$.

输出格式

一行，你的答案。

5
123 234 345 456 567

2

7
74 222 111111 185 13653 4237018 4218 19018

24157817

8
2 23 233 2333 23333 233333 2333333 2333333333333333333

1

数据范围

对于 $10\%$ 的数据，$n \leq 10,a_i \leq 30$。

对于 $20\%$ 的数据，$n \leq 10^3,a_i \leq 50$。

对于 $100\%$ 的数据，$1\le n \leq 10^5,1\le a_i \leq 10^7$。