CF815B.Karen and Test

Karen has just arrived at school, and she has a math test today!

The test is about basic addition and subtraction. Unfortunately, the teachers were too busy writing tasks for Codeforces rounds, and had no time to make an actual test. So, they just put one question in the test that is worth all the points.

There are n integers written on a row. Karen must alternately add and subtract each pair of adjacent integers, and write down the sums or differences on the next row. She must repeat this process on the values on the next row, and so on, until only one integer remains. The first operation should be addition.

Note that, if she ended the previous row by adding the integers, she should start the next row by subtracting, and vice versa.

The teachers will simply look at the last integer, and then if it is correct, Karen gets a perfect score, otherwise, she gets a zero for the test.

Karen has studied well for this test, but she is scared that she might make a mistake somewhere and it will cause her final answer to be wrong. If the process is followed, what number can she expect to be written on the last row?

Since this number can be quite large, output only the non-negative remainder after dividing it by 109 + 7.

凯伦刚刚到达学校，今天她有一场数学考试！

这场考试考察基础的加法与减法。不幸的是，老师们正忙于为 Codeforces 轮赛编写题目，没时间制作一份真正的试卷。因此，他们只在试卷中放入了一道题，而这道题的分值占整张试卷的全部分数。

一行上写有 $ n $ 个整数。凯伦必须对每一对相邻整数交替执行加法和减法运算，并将所得的和或差写在下一行。接着，她需对下一行中的数值重复该过程，依此类推，直至只剩下一个整数为止。第一个运算必须是加法。

注意：若她在上一行以加法结束，则下一行应以减法开始；反之亦然。

老师仅会查看最后剩下的那个整数：若其正确，凯伦得满分；否则，她得零分。

凯伦为这次考试做了充分准备，但她担心自己可能在某处出错，从而导致最终答案错误。如果严格按上述过程进行计算，最后一行将写出哪个数？

由于该数可能非常大，请仅输出它对 $ 10^9 + 7 $ 取模后的非负余数。

The first line of input contains a single integer n (1 ≤ n ≤ 200000), the number of numbers written on the first row.

The next line contains n integers. Specifically, the i-th one among these is a__i (1 ≤ a__i ≤ 109), the i-th number on the first row.

输入的第一行包含一个整数 $n$（$1 \leq n \leq 200000$），表示第一行中数字的个数。

下一行包含 $n$ 个整数。具体而言，其中第 $i$ 个数为 $a_i$（$1 \leq a_i \leq 10^9$），即第一行中的第 $i$ 个数。

Output a single integer on a line by itself, the number on the final row after performing the process above.

Since this number can be quite large, print only the non-negative remainder after dividing it by 109 + 7.

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

由于该数字可能非常大，请仅输出其除以 $10^9 + 7$ 后的非负余数。

In the first test case, the numbers written on the first row are 3, 6, 9, 12 and 15.

Karen performs the operations as follows:

The non-negative remainder after dividing the final number by 109 + 7 is still 36, so this is the correct output.

In the second test case, the numbers written on the first row are 3, 7, 5 and 2.

Karen performs the operations as follows:

The non-negative remainder after dividing the final number by 109 + 7 is 109 + 6, so this is the correct output.

在第一个测试用例中，第一行所写的数字为 3、6、9、12 和 15。

Karen 执行如下操作：

最终结果对 $10^9 + 7$ 取非负余数仍为 36，因此这是正确的输出。

在第二个测试用例中，第一行所写的数字为 3、7、5 和 2。

Karen 执行如下操作：

最终结果对 $10^9 + 7$ 取非负余数为 $10^9 + 6$，因此这是正确的输出。