데이트할래?

Leha는 Bankopolis에서의 생활에 지쳐 조용한 마을 Vičkopolis로 이사하기로 했다. 도착하자마자 그는 해킹한 컴퓨터의 네트워크를 확장하기 시작했다. 일주일 동안 Leha는 마을 전역에 있는 n대의 컴퓨터에 접근하는 데 성공했다. 공교롭게도 Vičkopolis에는 곧게 뻗은 거리가 단 하나뿐이기 때문에, Leha가 해킹한 모든 컴퓨터는 같은 직선 위에 놓여 있다.

이 거리에 좌표계를 정하자. 또한 해킹한 모든 컴퓨터에 1부터 n까지의 정수로 번호를 매기자. 그러면 i-th번 해킹된 컴퓨터는 점 xi에 위치한다. 또한 모든 컴퓨터의 좌표는 서로 다르다.

Leha는 힘든 일주일을 보낸 뒤 잠시 쉬기로 했다. 그래서 그는 친구 Noora를 식당에 초대하려 한다. 하지만 Noora는 단 하나의 조건, 즉 Leha가 간단한 문제를 풀어야 한다는 조건으로만 데이트에 동의한다.

Leha는 해킹한 모든 컴퓨터로 이루어진 집합의 공집합이 아닌 모든 부분집합 a에 대해 F(a)의 합을 계산해야 한다. 형식적으로, 1부터 n까지의 모든 정수로 이루어진 집합을 A라고 하자. Noora는 해커에게 식 의 값을 구하라고 한다. Here F(a)는 집합 a에 속한 모든 컴퓨터 쌍 사이 거리의 최댓값으로 계산한다. 형식적으로, . 필요한 합은 매우 클 수 있으므로 Noora는 이를 109 + 7로 나눈 나머지를 구하라고 한다.

하지만 Leha는 너무 지쳤다. 따라서 그는 이 문제를 풀 수 없다. 해커가 데이트에 갈 수 있도록 도와주자.

첫 번째 줄에는 해킹한 컴퓨터의 수를 나타내는 하나의 정수 n (1 ≤ n ≤ 3·105)이 주어진다.

두 번째 줄에는 해킹한 컴퓨터의 좌표를 나타내는 n개의 정수 x1, x2, ..., xn (1 ≤ xi ≤ 109)이 주어진다. 모든 xi이 서로 다름이 보장된다.

필요한 합을 109 + 7로 나눈 나머지를 나타내는 하나의 정수를 출력한다.

첫 번째 예제에는 공집합이 아닌 부분집합이 , , 의 세 개 있다. 첫 번째와 두 번째 부분집합은 합을 0만큼 증가시키고, 세 번째 부분집합은 합을 7 - 4 = 3만큼 증가시킨다. 따라서 답은 총 0 + 0 + 3 = 3이다.

두 번째 예제에는 공집합이 아닌 부분집합이 일곱 개 있다. 그중 다음 부분집합만 답을 증가시킨다: , , , . 따라서 합은 총 (4 - 3) + (4 - 1) + (3 - 1) + (4 - 1) = 9이다.