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 receiving the doctor's prescription, Watame went home only to realise the receipt has a different array from the recommendation given from the doctor. 

What was printed on the receipt 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 receipt 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 receipt 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

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

The next lines contains N integers S_i.

Output

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 receipt may be faulty), print -1 instead.

Example

Input 1:
6
1 2 3 4 5 6

Output 1:
1

Input 2:
5
3 3 3 3 4

Output 2:
250000002

Input 3:
2
4 1

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⁹