Capsaicin Tastes Good in Spring

Juheon loves spicy food. To be precise, he is a true thrill-seeker who finds joy in the pain that spicy food brings.

The concentration of capsaicin, the compound behind the heat of chili peppers, is measured in Scoville units. The heat Juheon feels does not depend on the absolute value of any single dish, but on the relative spread among the dishes eaten together. Eating dishes with Scoville values $5, 2, 8$ feels as hot as $8 - 2 = 6$, the difference between the highest value $8$ and the lowest value $2$. For any group of dishes, define its pain index as the difference between the maximum and the minimum Scoville value in the group.

Juheon recently found a favorite spicy restaurant that lists the Scoville value of every dish on its menu. His goal is to taste every possible combination of dishes, but he is picky and never eats the same combination twice. Compute the sum of the pain indices over every subset of dishes of size at least $2$.

The first line contains the total number of dishes $N$. The second line contains the $N$ Scoville values, separated by spaces. Each Scoville value is an integer between $0$ and $2^{31}-1$ inclusive.

Print, on one line, the sum of the pain indices over all combinations, modulo $1000000007$. A single-dish combination has pain index $0$ and does not change the sum.