DeMen100ms là 1 con người đang ở tận cùng của sự cô đơn. Và cậu luôn ghét nhìn thấy người khác đi chơi với nhau. Một hôm, leanhduy123 rủ cậu đi ngồi cafe vỉa hè. Vì thấy mọi người ngoài đường đi chơi cùng nhau nên DeMen100ms rất cay cú.

• Ở ngoài đường đang có \(N\) người được đánh số từ \(1\) đến \(N\).
• Người thứ i có điểm hạnh phúc là \(HP[i]\).
• Tổng số điểm hạnh phúc là : tổng của các tích \(HP[i] * HP[j]\) \((1 \leq i < j \leq n)\)

Yêu cầu: In ra tổng số điểm hạnh phúc có thể đạt được từ \(N\) người đó.

Input

• Dòng đầu nhập \(N\) là người trên đường.
• Dòng thứ 2 là \(N\) số điểm hạnh phúc của \(N\) người.

Output

• In ra tổng điểm hạnh phúc của \(N\) người đó, vì kết quả có thể rất lớn nên lấy kết quả modulo cho \(10^9 + 7\)

Constraints

• \(N \leq 5*10^6\)
• \(0 < HP[i] \leq 3*10^4\)

Scoring

• Subtask \(1\) (\(40\%\) số điểm): \(N \leq 5*10^3\).
• Subtask \(2\) (\(60\%\) số điểm): Không có ràng buộc gì thêm.

Example

3
1 2 3 

11