너 봄에는 캡사이신이 맛있단다

주헌이는 매운맛을 좋아한다. 정확히 말하면, 매운 음식을 먹고 느끼는 고통 자체에서 즐거움을 느끼는 사람이다.

고추의 매운맛 성분인 캡사이신의 농도를 수치화한 단위를 스코빌 지수라고 한다. 주헌이가 느끼는 매운 정도는 메뉴 각각의 절대적인 수치가 아니라, 함께 먹는 음식들 사이의 상대적인 차이로 정해진다. 스코빌 지수가 $5, 2, 8$인 음식들을 함께 먹으면, 가장 높은 수치 $8$과 가장 낮은 수치 $2$의 차이인 $8 - 2 = 6$만큼의 매운맛을 느낀다. 이렇게 함께 먹는 메뉴들의 스코빌 지수 중 최댓값과 최솟값의 차이를 고통지수라고 정의한다.

최근 주헌이는 좋아하는 매운맛 전문점을 찾았다. 이 음식점은 모든 메뉴의 스코빌 지수를 메뉴판에 공개하고 있다. 주헌이의 목표는 이 음식점의 메뉴들로 만들 수 있는 모든 조합을 먹는 것이다. 단, 주헌이는 까다로워서 한 번 먹어 본 조합은 다시 먹지 않는다. 크기가 $2$ 이상인 모든 부분집합에 대해 고통지수를 구하고, 그 총합을 구해보자.

첫째 줄에 메뉴의 총 개수 $N$이 주어진다. 둘째 줄에 $N$개의 메뉴 각각의 스코빌 지수가 공백으로 구분되어 주어진다. 모든 스코빌 지수는 $0$보다 크거나 같고 $2^{31}-1$보다 작거나 같은 정수이다.

크기가 $2$ 이상인 모든 메뉴 조합에 대한 고통지수의 합을 $1000000007$로 나눈 나머지를 한 줄에 출력한다. 메뉴가 하나뿐인 조합의 고통지수는 $0$이므로 합에 영향을 주지 않는다.