Cho N sợi dây, biết chi phí nối 2 sợ dây là tổng độ dài của 2 sợi dây đó. Nhiệm vụ của bạn là nối N sợi dây này thành 1 sao cho chi phí nối dây là lớn nhất

Input Format

Dòng 1 chứa số nguyên N; Dòng 2 chứa N số nguyên là độ dài các sợ dây. (1<=N<=10^5; Các sợi dây có độ dài không quá 10^9)

Constraints

.

Output Format

Đáp án của bài toán chia dư với 10^9 + 7.

Ví dụ:

Dữ liệu vào

6
7 7 6 10 4 8

Dữ liệu ra

155