Fibonacci numbers have the following form F1=1, F2=1, F3=2 ... Fn=Fn-1 +Fn-2 .

We have an array { a1,a2,...,aN} which contains N elements. We want to find gcd(F{a1},F{a2},F{a3},...,F{aN}).

InputFormat

The first line contains N, where N denotes size of the array. Each of the next N lines contains a number: the i line contains ai.

Output Format

Print a single integer—the remainder of the division of the resulting number by 1000000007.

Constraints

1<=N<=2*10^5

1<=ai<=10^12

Sample Input

3

2

3

5

Sample Output

11

Explanation

F2=1

F3=2

F5=5

gcd(1,2,5)=1

SampleInput

2

3

6

Sample Output

2

Explanation

F3=2

F6=8

gcd(2,8)=2