B. Карен и тест
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Карен только что пришла в школу, у нее сегодня тест по математике!

Тест проверяет умения складывать и вычитать числа. К сожалению, учителя были заняты подготовкой задач к раунду Codeforces, поэтому у них не было времени сделать тест. Поэтому они дали лишь одну задачу, которая стоит все баллы.

В ряд записаны n целых чисел. Карен должна по очереди складывать и вычитать каждую пару соседних чисел, и записывать получающиеся суммы или разности в следующий ряд. Затем она должна повторить процесс со следующим рядом, и так далее, пока не останется ровно одно число. Первой операцией должно быть сложение.

Заметьте, что, если она закончила предыдущий ряд, вычислив сумму чисел, то она должна начать новый ряд вычитанием, и наоборот.

Учителя просто посмотрят на последнее число: если оно окажется верным, то Карен получит полный балл, иначе — ноль.

Карен хорошо подготовилась к тесту, но боится сделать ошибку где-нибудь, что приведет ее к неправильному финальному ответу. Можете вычислить, какое число она должна получить в конце?

Так как это число может быть большим, выведите неотрицательный остаток от его деления на 109 + 7.

Входные данные

Первая строка содержит одно целое число n (1 ≤ n ≤ 200000) — количество чисел, записанных в первом ряду.

Вторая строка содержит n целых чисел. А именно, i-е из этих чисел равно ai (1 ≤ ai ≤ 109) — i-му числу в первом ряду.

Выходные данные

Выведите одно целое число: число в последнем ряду после выполнения всех операций.

Так как оно может быть большим, выведите его неотрицательный остаток от деления на 109 + 7.

Примеры
Входные данные
5
3 6 9 12 15
Выходные данные
36
Входные данные
4
3 7 5 2
Выходные данные
1000000006
Примечание

В первом примере числа в первом ряду равны 3, 6, 9, 12 и 15.

Карен выполняет операции как показано на рисунке:

Неотрицательный остаток от деления итогового числа на 109 + 7 равен 36.

Во втором примере числа в первом ряду равны 3, 7, 5 и 2.

Карен выполняет следующие операции:

Неотрицательных остаток от деления итогового числа на 109 + 7 равен 109 + 6.