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

SAMPLE INPUT
3
2
3
5

SAMPLE OUTPUT
1

见题面

见题面