CF1788D.Moving Dots

We play a game with $n$ dots on a number line.

The initial coordinate of the $i$-th dot is $x_i$. These coordinates are distinct. Every dot starts moving simultaneously with the same constant speed.

Each dot moves in the direction of the closest dot (different from itself) until it meets another dot. In the case of a tie, it goes to the left. Two dots meet if they are in the same coordinate, after that, they stop moving.

After enough time, every dot stops moving. The result of a game is the number of distinct coordinates where the dots stop.

Because this game is too easy, calculate the sum of results when we play the game for every subset of the given $n$ dots that has at least two dots. As the result can be very large, print the sum modulo $10^9+7$.

我们在一条数轴上有 $n$ 个点进行一个游戏。

第 $i$ 个点的初始坐标为 $x_i$，这些坐标互不相同。每个点同时以相同的恒定速度开始运动。

每个点均朝向离它最近的（且不同于自身的）点移动，直至与另一个点相遇。若存在多个距离相等的最近点，则向左移动。当两个点到达同一坐标时即视为相遇，此后它们停止运动。

经过足够长的时间后，所有点均停止运动。游戏的结果定义为所有点最终停止位置中不同坐标的个数。

由于该游戏过于简单，请计算：对给定的 $n$ 个点的每一个至少包含两个点的子集，分别进行上述游戏，并将所有游戏结果求和。由于结果可能非常大，请输出该和对 $10^9+7$ 取模的值。

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 \lt x_2 \lt \ldots \lt x_n \leq 10^9$), where $x_i$ represents the initial coordinate of $i$-th dot.

第一行包含一个整数 $n$（$2 \leq n \leq 3000$）。

第二行包含 $n$ 个整数 $x_1, x_2, \ldots, x_n$（$1 \leq x_1 \lt x_2 \lt \ldots \lt x_n \leq 10^9$），其中 $x_i$ 表示第 $i$ 个点的初始坐标。

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

输出结果之和对 $10^9+7$ 取模的值。

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.

在第一个例子中，对于大小为 $2$ 的子集，两个点彼此相向移动，因此存在 $1$ 个点停止的坐标。

对于大小为 $3$ 的子集，第一个点和第三个点均向第二个点移动，因此无论第二个点朝哪个方向移动，最终都只有 $1$ 个点停止的坐标。

对于 $[1, 2, 4, 6]$，第一个点和第二个点彼此相向移动。对于第三个点，初始时第二个点和第四个点是距离它最近的点；由于距离相等（平局），第三个点向左移动。第四个点也向左移动。因此，点最终停止于唯一坐标 $1.5$，即存在 $1$ 个停止坐标。

由于共有 $6$ 个大小为 $2$ 的子集、$4$ 个大小为 $3$ 的子集以及 $1$ 个大小为 $4$ 的子集，答案为 $6 \cdot 1 + 4 \cdot 1 + 1 = 11$。

在第二个例子中，对于大小为 $5$ 的子集（点位于 $1$、$3$、$5$、$11$、$15$ 处），位于 $1$ 和 $11$ 的点向右移动，而位于 $3$、$5$、$15$ 的点向左移动。位于 $1$、$3$、$5$ 的点最终将在 $2$ 处相遇，位于 $11$ 和 $15$ 的点将在 $13$ 处相遇，因此共有 $2$ 个点停止的坐标。