Карен только что пришла в школу, у нее сегодня тест по математике!
Тест проверяет умения складывать и вычитать числа. К сожалению, учителя были заняты подготовкой задач к раунду Codeforces, поэтому у них не было времени сделать тест. Поэтому они дали лишь одну задачу, которая стоит все баллы.
В ряд записаны n целых чисел. Карен должна по очереди складывать и вычитать каждую пару соседних чисел, и записывать получающиеся суммы или разности в следующий ряд. Затем она должна повторить процесс со следующим рядом, и так далее, пока не останется ровно одно число. Первой операцией должно быть сложение.
Заметьте, что, если она закончила предыдущий ряд, вычислив сумму чисел, то она должна начать новый ряд вычитанием, и наоборот.
Учителя просто посмотрят на последнее число: если оно окажется верным, то Карен получит полный балл, иначе — ноль.
Карен хорошо подготовилась к тесту, но боится сделать ошибку где-нибудь, что приведет ее к неправильному финальному ответу. Можете вычислить, какое число она должна получить в конце?
Так как это число может быть большим, выведите неотрицательный остаток от его деления на 109 + 7.
Выходные данные
Выведите одно целое число: число в последнем ряду после выполнения всех операций.
Так как оно может быть большим, выведите его неотрицательный остаток от деления на 109 + 7.
Примечание
В первом примере числа в первом ряду равны 3, 6, 9, 12 и 15.
Карен выполняет операции как показано на рисунке:
Неотрицательный остаток от деления итогового числа на 109 + 7 равен 36.
Во втором примере числа в первом ряду равны 3, 7, 5 и 2.
Карен выполняет следующие операции:
Неотрицательных остаток от деления итогового числа на 109 + 7 равен 109 + 6.