Description

Input

The first line contains one integer $n$ ($2 \leq n \leq 3000$).

The next line contains $n$ integers $x_1, x_2, \ldots, x_n$ ($1 \leq x_1 < x_2 < \ldots < x_n \leq 10^9$), where $x_i$ represents the initial coordinate of $i$-th dot.

Output

Print the sum of results modulo $10^9+7$.

4
1 2 4 6

11

5
1 3 5 11 15

30

Note

In the first example, for a subset of size $2$, two dots move toward each other, so there is $1$ coordinate where the dots stop.

For a subset of size $3$, the first dot and third dot move toward the second dot, so there is $1$ coordinate where the dots stop no matter the direction where the second dot moves.

For $[1, 2, 4, 6]$, the first and second dots move toward each other. For the third dot, initially, the second dot and the fourth dot are the closest dots. Since it is a tie, the third dot moves left. The fourth dot also moves left. So there is $1$ coordinate where the dots stop, which is $1.5$.

Because there are $6$ subsets of size $2$, $4$ subsets of size $3$ and one subset of size $4$, the answer is $6 \cdot 1 + 4 \cdot 1 + 1 = 11$.

In the second example, for a subset of size $5$ (when there are dots at $1$, $3$, $5$, $11$, $15$), dots at $1$ and $11$ will move right and dots at $3$, $5$, $15$ will move left. Dots at $1$, $3$, $5$ will eventually meet at $2$, and dots at $11$ and $15$ will meet at $13$, so there are $2$ coordinates where the dots stop.