Дано масив \(A\) із \(N\) цілих чисел.

Ваше завдання --- написати програму для знаходження максимального значення \(∑(arr[i]*i)\), де \(i = 0, 1, 2,., n-1\).

Дозволяється змінювати порядок елементів масиву.

Примітка. Оскільки результат може бути великим, тому виведіть його по модулю \(10^9+7\).

Формат вхідних даних

Перший рядок вхідного потоку містить ціле число \(N\).

Наступний рядок містить \(N\) цілих чисел \(A_i\).

Числа у рядку розділяються пропуском.

Формат вихідних даних

У вихідний потік вивести відповідь.

Обмеження

\(1 \le N \le 10^7\)

\(1 \le A_i \le N\)

Приклад вхідних даних

5
5 3 2 4 1

Приклад вихідних даних

40

Приклад вхідних даних

3
3 2 1

Приклад вихідних даних

8