Fibonacci numbers have the following form: 

                                                                      F(1) = 1

                                                                      F(2)= 1

                                                                      F(3) = 2

                                                                          :

                                                                      F(n) = F(n-2) + F(n-1)

We have an array a1 , a2 , a3 ...... upto n elements .

We want to find gcd( F(a1) , F(a2) .......  F(an) .

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<= n <= 2 * 10^5

 *  1 <= a(i) <= 10^12

Sample Input 1

3
2
3
5

Sample Output 1

1

Explanation 1 
 
 F(2) = 1

 F(3) = 2

 F(5) = 5

gcd(1,2,5) = 1
  

Sample Input 2

2
3
6

Sample Output 2

2

Explanation 2 
 
 F(3) = 2

 F(6) = 8

gcd(2,8) = 2