D. Движущиеся точки
ограничение по времени на тест
1.5 секунд
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Вы играете в игру с $$$n$$$ точками на числовой прямой.

Изначальная координата $$$i$$$-й точки равна $$$x_i$$$. Координаты всех точек различны. Каждая точка начинает двигаться одновременно с одинаковой постоянной скоростью.

Каждая точка движется в направлении к ближайшей точке (отличной от нее самой), пока не встретится с какой-либо точкой. В случае равенства до ближайшей точки слева и справа, точка движется влево. Две точки встречаются, если их координаты совпадают, при этом они навсегда прекращают движение.

Через некоторое время все точки перестанут двигаться. Результатом игры является количество различных координат, в которых остановятся точки.

Поскольку эта игра слишком проста, подсчитайте сумму результатов игр для каждого подмножества из данных $$$n$$$ точек, в котором есть хотя бы две точки. Так как ответ может быть очень большим, выведите его по модулю $$$10^9+7$$$.

Входные данные

Первая строка содержит одно целое число $$$n$$$ ($$$2 \leq n \leq 3000$$$).

Следующая строка содержит $$$n$$$ целых чисел $$$x_1, x_2, \ldots, x_n$$$ ($$$1 \leq x_1 < x_2 < \ldots < x_n \leq 10^9$$$), где $$$x_i$$$ является координатой $$$i$$$-й точки.

Выходные данные

Выведите сумму результатов по модулю $$$10^9+7$$$.

Примеры
Входные данные
4
1 2 4 6
Выходные данные
11
Входные данные
5
1 3 5 11 15
Выходные данные
30
Примечание

В первом примере для подмножества размером $$$2$$$ две точки движутся навстречу друг другу, поэтому существует $$$1$$$ координата, где точки останавливаются.

Для подмножества размером $$$3$$$ первая точка и третья точка движутся ко второй точке, поэтому существует $$$1$$$ координата, где точки останавливаются, вне зависимости от направления движения второй точки.

Для подмножества $$$[1, 2, 4, 6]$$$ первая и вторая точки движутся навстречу друг другу. Для третьей точки изначально вторая точка и четвертая точка являются ближайшими точками. Из-за этого равенства третья точка движется влево. Четвертая точка также движется влево. Таким образом, существует $$$1$$$ координата, где точки останавливаются, которая равна $$$1.5$$$.

Поскольку существует $$$6$$$ подмножеств размером $$$2$$$, $$$4$$$ подмножеств размером $$$3$$$ и одно подмножество размером $$$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$$$ координаты, где точки остановятся.