Cho một dãy gồm n số nguyên dương \(a_1,a_2,…,a_n\).
Hãy tính giá trị biểu thức sau:

\(S=\sum_{i=1}^{n-2}\sum_{j=i+1}^{n-1}\sum_{k=j+1}^{n} a_i\times (a_j\times a_k-1)\)

Input

• Dòng đầu tiên là số nguyên dương \(n. (3\le n\le 10^5 ).\)
• Dòng thứ hai gồm \(n\) số nguyên dương \(a_1,a_2,…,a_n (a_i\le 10^9).\)

Output

• In ra giá trị \(S \mod 1000000007\).

Scoring

• Subtask \(1\) (\(40\%\) số điểm): \(n\le 100\)
• Subtask \(2\) (\(30\%\) số điểm): \(n\le 1000\)
• Subtask \(3\) (\(30\%\) số điểm): \(n\le 10^5\)

Example

4
1 2 3 4 

45