Cho mảng A[] gồm N phần tử.Nhiệm vụ của bạn là tìm giá trị lớn nhất của tổng bên dưới bằng cách sắp đặt lại các phần tử trong mảng. Chú ý, kết quả của bài toán có thể rất lớn vì vậy bạn hãy đưa ra kết quả lấy modulo với 10^9+7.

Input Format

Dòng đầu tiên là số nguyên N. Dòng tiếp theo gồm N số nguyên A[i]. (1≤ N ≤ 10^5; 0 ≤ A[i] ≤ 10^7)

Output Format

In ra kết quả của bài toán lấy dư với (10^9 + 7)

Ví dụ:

Dữ liệu vào:

5
1 2 3 4 5

Dữ liệu ra:

40