Fibonacci numbers have the following form:

$\begin{aligned}F_1&-1\\ F_2&=1\\ F_3&=2\\ \vdots\\ F_n&=F_{n-2}+F_{n-1}\end{aligned}$

We have an array $a_1,a_2,\ldots,a_N$ which contains $N$ elements.

We want to find $\text{gcd}(F_{a_1},F_{a_2},F_{a_3},...,F_{a_N})$.

Input Format

The first line contains $N$, where $N$ denotes size of the array.

Each of the next $N$ lines contains a number: the $i^{th}$ line contains $a_i$.

Output Format

Print a single integer — the remainder of the division of the resulting number by $10^9+7$.

Constraints

$1\leq N\leq2\times10^5$

$1\leq a_i\leq10^{12}$

Sample Input 1

3
2
3
5

Sample Output 1

1

Explanation 1

$F_{2}=1$

$F_3=2$

$F_5=5$

$\text{gcd}(1,2,5)=1$

Sample Input 2

2
3
6

Sample Output 2

2

Explanation 2

$F_3=2$

$F_6=8$

$\text{gcd}(2,8)=2$

见题面

见题面