Для двох послідовностей \(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