Cho \(n\) sợi dây với độ dài khác nhau được lưu trong mảng \(a\). Nhiệm vụ của bạn là nối \(n\) sợi dây thành một sợi sao cho tổng chi phí nối dây là nhỏ nhất. Biết chi phí nối sợi dây thứ \(i\) và sợi dây thứ \(j\) là tổng độ dài hai sợi dây \(a_i\) và \(a_j\).

Input

• Dòng đầu tiên chứa số nguyên \(n\) (\(n \leq 2 \times 10^6\)).
• Dòng thứ hai gồm \(n\) số nguyên dương \(a_i\) (\(1 \leq a_i \leq 10^9\)).

Output

In ra đáp án theo modulo \(10^9 + 7\).

Example

7
2 4 1 2 10 2 3

59