Вы играете в игру с \(n\) точками на числовой прямой.
Изначальная координата \(i\)-й точки равна \(x_i\). Координаты всех точек различны. Каждая точка начинает двигаться одновременно с одинаковой постоянной скоростью.
Каждая точка движется в направлении к ближайшей точке (отличной от нее самой), пока не встретится с какой-либо точкой. В случае равенства до ближайшей точки слева и справа, точка движется влево. Две точки встречаются, если их координаты совпадают, при этом они навсегда прекращают движение.
Через некоторое время все точки перестанут двигаться. Результатом игры является количество различных координат, в которых остановятся точки.
Поскольку эта игра слишком проста, подсчитайте сумму результатов игр для каждого подмножества из данных \(n\) точек, в котором есть хотя бы две точки. Так как ответ может быть очень большим, выведите его по модулю \(10^9+7\).
Примечание
В первом примере для подмножества размером \(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\) координаты, где точки остановятся.