Trong tháng vừa qua có rất nhiều vụ mất xe làm cho Iris rất hoang mang. Vì vậy anh ta có ý định là sẽ mua xích để đi đâu anh cũng không cần quan tâm đến vấn đề xe cộ nữa. Khi biết tin đó thì các bạn Iris đã tặng anh ~n~ dây xích.

Tuy nhiên, Iris lại có 1 niềm đam mê khác ngoài xếp hình đó là ngồi nối dây nên anh muốn làm xích lớn hơn từ ~n~ dây xích được tặng. Iris khá vụng về, không biết cách nào để nối đồng thời ~n~ xích với nhau. Thời gian để tạo ra một chiếc xích mới từ ~2~ chiếc xích có độ dài ~a~ và ~b~ mất tổng cộng ~a + b~ phút.

Các bạn hãy tính giúp Iris xem cần ít nhất bao nhiêu thời gian để có thể làm xong được chiếc xích mong muốn của mình?

Input

• Dòng đầu tiên là số nguyên ~n~ (~1 \le n \le 2 \cdot 10^5~).
• Dòng tiếp theo gồm ~n~ số nguyên dương ~c_i~ (~1 \le c_i \le 10^9~).

Output

In ra đáp án của bài toán theo modulo ~10^9+7~.

Sample

Input #1

7
2 4 1 2 10 2 3

Output #1

59

Problem source: CLB Lập Trình PTIT