Watame needs to consume asacoco. However, consuming too much asacoco can be dangerous, so she consults with a doctor.

The doctor recommends her a limit for every day. Let A_i be a real number denoting the limit of asacoco allowed to be consumed in the i-th day.

Uniquely, the array A_i is a non-decreasing arithmetic sequence.

An element A_i can be represented as A₀ + i * d where d is a constant real number. It is guaranteed that A₀ is an integer.

After recieving the doctor's prescription, Watame went home only to realise the reciept has a different array from the recommendation given from the doctor. 

What was printed on the reciept was an array of integers S_i with a note that S_i = [A_i].

Here, [x] denotes the largest integer less than or equal to x (floor function).

For rehabilitation, Watame is forced to minimize d (since minimizing d minimizes A_i too, thus less asacoco for Watame) such that the information printed on the reciept is still valid.

If there exists a valid d, it can be represented as a fraction P / Q where GCD(P, Q) = 1. Print the answer in the form of P * Q^-1 modulo 10⁹ + 7.

There can be cases where the reciept can be faulty (the cashier and the doctor may as well be drunk of asacoco) and there is no valid d. In this case, print -1 instead.

Input Format

The first line contains an integer N, the size of the array S.

The next lines contains N integers S_i.

Output Format

Print an integer representing the answer in the form of P * Q^-1 modulo 10⁹ + 7.

If there does not exist a valid d (the reciept may be faulty), print -1 instead.

Sample Input 1

6

1 2 3 4 5 6

Sample Output 1

1

Sample Input 2

5

3 3 3 3 4

Sample Output 2

250000002

Sample Input 3

2

4 1

Sample Output 3

-1

Explanation

The answers for sample 1 and 2 in decimal format is 1.0 and 0.25 respectively.

Constraints

1 ≤ N ≤ 10⁵

1 ≤ S_i ≤ 10⁹