Для двох послідовностей ~S~ і ~T~ довжини ~N~, що складаються з 0 і 1, визначимо ~f(S, T)~ таким чином:

• Розглянемо повторення наступної операції над ~S~ так, щоб ~S~ дорівнювала ~T~. ~f(S, T)~ --- мінімально можлива загальна вартість цих операцій.

  ---Змінити ~S_i~(з 0 на 1 або навпаки). Вартість цієї операції дорівнює ~D \times C_i~, де ~D~ --- кількість цілих чисел ~j~, таких що ~S_j \neq T_j~ (~1 \leq j \leq N~) безпосередньо перед цією зміною.

Існує ~2^N \times (2^N - 1)~ пар (~S, T~) різних послідовностей довжини ~N~, що складаються з 0 і 1.

Обчисліть суму ~f(S, T)~ над усіма цими парами за модулем (~10^9 + 7~).

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

Перший рядок вхідного потоку містить ціле число ~N~ (~1 \le N \le 2 \times 10^5~)

Наступний рядок містить ~N~ цілих чисел ~C_i~ (~1 \le C_i \le 10^9~).

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

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

У вихідний потік вивести шукану суму.

Примітка

До прикладу 1:

Існують дві пари (~S, T~) різних послідовностей довжиною 2, які складаються з 0 і 1, а саме:

• ~S = (0), T = (1)~: змінюючи ~S_1~ на 1, ми можемо отримати ~S = T~ за ціною 1000000000, отже, ~f(S, T) = 1000000000~.

• ~S = (1), T = (0)~: змінюючи ~S_1~ на 0, ми можемо отримати ~S = T~ за ціною 1000000000, тому ~f(S , T) = 1000000000~.

Сума їх дорівнює 2000000000, і ми повинні вивести її за модулем (~10^9 + 7~), тобто 999999993.

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

1
1000000000

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

999999993

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

2
5 8

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

124

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

5
52 67 72 25 79

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

269312