• محدودیت زمان: ۱ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

---

منظور از مشق یک مجموعه \(k\) عضوی جمع \(\lfloor\frac{k}{2}\rfloor\) عضو بزرگ‌تر منهای \(\lceil\frac{k}{2}\rceil\) عضو کوچک‌تر آن است. برای مثال مشق مجموعه‌ی \(\{2, 3, 7\}\) برابر \(7-3-2=2\) و مشق مجموعه‌ی \({1, 2, 3, 4}\) برابر \(4 + 3 - 2 - 1 = 4\) است. مشق مجموعه‌ی تهی را صفر در نظر بگیرید.

اعضای یک مجموعه‌ی \(n\) عضوی از اعداد صحیح را داریم، می‌خواهیم به ازای تمام \(2^n\) زیرمجموعه ممکن از این مجموعه، مشق آن‌ها را با هم جمع کنیم. از شما می‌خواهیم برنامه‌ای بنویسید که این مقدار را حساب کند. (برای بهتر متوجه شدن سوال، مثال اول را مطالعه کنید.)

چون ممکن است حاصل خیلی بزرگ باشد، باقی‌مانده‌ی پاسخ را بر \(10^9 + 7\) محاسبه کنید.

ورودی

در خط اول عدد \(n\) و سپس در خط بعد \(n\) عدد صحیح \(a_i\) با فاصله از هم ورودی داده می‌شوند.

\[1 \le n \le 5000\] \[1 \le a_i \le 1000 \, 000\]

تضمین می‌شود که \(a_1 \lt a_2 \lt \dots \lt a_n\,\) باشد.

خروجی

حاصل جمع مورد نظر را خروجی دهید.

مثال

ورودی نمونه ۱

4
1 2 3 7

خروجی نمونه ۱

22

\[ \begin{array}{ccc} \{\} & \to & 0 \\ \{ 2 \} & \to & -2 \\ \{ 7 \} & \to & -7 \\ \{ 1 \} & \to & -1 \\ \{ 3 \} & \to & -3 \\ \{ 2, 7 \} & \to & 7 - 2 = 5 \\ \{ 1, 2 \} & \to & 2 - 1 = 1 \\ \{ 2, 3 \} & \to & 3 - 2 = 1 \\ \{ 1, 7 \} & \to & 7 - 1 = 6 \\ \{ 3, 7 \} & \to & 7 - 3 = 4 \\ \{ 1, 3 \} & \to & 3 - 1 = 2 \\ \{ 1, 3, 7 \} & \to & 7 - 3 - 1 = 3\\ \{ 1, 2, 3 \} & \to & 3 - 2 - 1 = 0 \\ \{ 2, 3, 7 \} & \to & 7 - 3 - 2 = 2 \\ \{ 1, 2, 7 \} & \to & 7 - 2 - 1 = 4 \\ \{ 1, 2, 3, 7 \} & \to & 7 + 3 - 2 - 1 = 7\\ \end{array} \]

بنابراین حاصل جمع برابر است با: \[0 - 2 - 7 -1 -3 + 5 + 1 + 1 + 6 + 4 + 2 + 3 + 0 + 2 + 4 + 7 = 22\]

ورودی نمونه ۲

3
1 2 3

خروجی نمونه ۲

1000000005

\[ \begin{array}{ccc} \{\} & \to & 0 \\ \{ 1 \} & \to & -1 \\ \{ 2 \} & \to & -2 \\ \{ 3 \} & \to & -3 \\ \{ 1, 2 \} & \to & 2 - 1 = 1\\ \{ 1, 3 \} & \to & 3 - 1 = 2 \\ \{ 2, 3 \} & \to & 3 - 2 = 1 \\ \{ 1, 2, 3 \} & \to & 3 - 2 - 1 = 0 \\ \end{array} \]

بنابراین حاصل جمع برابر است با: \[0 - 1 -2 -3 + 1 + 2 + 1 + 0 = -2\]

توجه کنید باقی‌مانده‌ی \(-2\) بر \(1000,000,007\) برابر \(1000,000,005\) است.