2746. 凯伦和测试

【题目描述】

凯伦刚到学校，今天有数学考试！

测试是关于基本的加法和减法。不幸的是，老师们忙于编写代码的任务，没有时间进行实际的测试。因此他们只出了一道测试题：

有n个整数排成一行，凯伦必须交替地加和减每对相邻的整数，并在下一行写下和或差，她必须重复这个操作直到只剩下一个数。第一个操作应当是加法。需要注意的是，如果她通过加法结束上一行，就必须用减法开始下一行，反之亦然。

老师只会看一下最后一个整数，如果是正确的，凯伦就会得到一个完美的分数，否则，她会得到零分。

凯伦为了这个测试做了充足的准备，但是她害怕出错，因此希望你能告诉她答案。

由于数字可能很大，输出答案模10^9+7的非负余数。

【输入格式】

第一行输入包含一个整数n（1≤n≤200000），写在第一行的数字个数。下一行包含n个整数。具体而言，这些中的第i个是ai（1≤ai≤10^9），即第1行的第i个数。

【输出格式】

在一行上输出单个整数，就是执行上述过程后最后一行的数字。

【样例1】

input



5



3 6 9 12 15



output



36

【样例2】

input



4



3 7 5 2



output



1000000006

【提示】

在此键入。

【来源】

在此键入。