凯伦刚到学校,今天有数学考试!
测试内容是基本加法和减法。不幸的是,老师们忙于编写 Codeforces 轮次的任务,没有时间进行实际测试。因此,他们只是在测试中提出了一个值得所有分数的问题。
一行写有n个整数。凯伦必须交替对每对相邻整数进行加减运算,并在下一行写下总和或差值。她必须对下一行的值重复此过程,依此类推,直到只剩下一个整数。第一个运算应该是加法。
请注意,如果她通过添加整数来结束前一行,则她应该通过减法开始下一行,反之亦然。
老师们只会看最后一个整数,如果正确,凯伦就得满分,否则,她的考试得零分。
Karen在这次考试中学习得很好,但她担心自己可能会在某个地方犯错,从而导致她最终的答案是错误的。如果按照这个过程,她预计最后一行会写出什么数字?
由于这个数字可能很大,因此仅输出除以 109 + 7 后的非负余数。
输入
输入的第一行包含一个整数 n (1 ≤ n ≤ 200000),即第一行写入的数字数量。
下一行包含 n 个整数。具体来说,其中第 i 个是 ai (1 ≤ ai ≤ 109),即第一行的第 i 个数字。
输出
在一行上单独输出一个整数,即执行上述过程后最后一行的数字。
由于该数字可能非常大,因此仅打印除以 109 + 7 后的非负余数。
示例
输入 #1
5 3 6 9 12 15
输出 #1
36
输入 #2
4 3 7 5 2
输出 #2
1000000006
注意
在第一个测试用例中,第一行写入的数字是 3、6、9、12 和 15。
Karen 执行的操作如下:
最终数字除以 109 + 7 后的非负余数仍然是 36,因此这是正确的输出。
在第二个测试用例中,第一行写的数字是 3、7、5 和 2。
Karen 执行的操作如下:
最终数字除以 109 + 7 后的非负余数为 109 + 6,因此这是正确的输出。