题目背景

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$。