Solve the programming task below in a Python markdown code block.
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$