Karen has just arrived at school, and she has a math test today!
<center></center>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.
## Input
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.
## Output
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.
[samples]
## Note
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:
<center></center>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:
<center></center>The non-negative remainder after dividing the final number by 109 + 7 is 109 + 6, so this is the correct output.
Karen 刚到学校，今天有一场数学测验！
测验内容是基本的加法和减法。不幸的是，老师们忙于为 Codeforces 比赛出题，没有时间制作真正的测验题，因此他们只在测验中放了一道题，这道题占全部分数。
一行上写了 #cf_span[n] 个整数。Karen 必须交替地对每一对相邻整数进行加法和减法，并将结果写在下一行。她必须对下一行的数值重复此过程，直到只剩下一个整数为止。第一次操作应为加法。
请注意，如果她在上一行以加法结束，则下一行应以减法开始，反之亦然。
老师只会查看最后一个整数，如果正确，Karen 将获得满分；否则，她将得零分。
Karen 为这次测验复习得很充分，但她担心自己可能在某个地方出错，导致最终答案错误。如果按照上述过程进行，她可以预期最后一行写下的数字是多少？
由于这个数字可能非常大，只需输出其对 #cf_span[109 + 7] 取非负余数后的结果。
输入的第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 200000])，表示第一行上写的数字个数。
第二行包含 #cf_span[n] 个整数。具体地，其中第 #cf_span[i] 个数是 #cf_span[ai] (#cf_span[1 ≤ ai ≤ 109])，即第一行的第 #cf_span[i] 个数。
请输出一行一个整数，表示经过上述过程后最后一行的数字。
由于这个数字可能非常大，只需输出其对 #cf_span[109 + 7] 取非负余数后的结果。
在第一个测试用例中，第一行的数字为 #cf_span[3]、#cf_span[6]、#cf_span[9]、#cf_span[12] 和 #cf_span[15]。
Karen 执行的操作如下：
最终数字对 #cf_span[109 + 7] 取非负余数后仍为 #cf_span[36]，因此这是正确输出。
在第二个测试用例中，第一行的数字为 #cf_span[3]、#cf_span[7]、#cf_span[5] 和 #cf_span[2]。
Karen 执行的操作如下：
最终数字对 #cf_span[109 + 7] 取非负余数后为 #cf_span[109 + 6]，因此这是正确输出。
## Input
输入的第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 200000])，表示第一行上写的数字个数。第二行包含 #cf_span[n] 个整数。具体地，其中第 #cf_span[i] 个数是 #cf_span[ai] (#cf_span[1 ≤ ai ≤ 109])，即第一行的第 #cf_span[i] 个数。
## Output
请输出一行一个整数，表示经过上述过程后最后一行的数字。由于这个数字可能非常大，只需输出其对 #cf_span[109 + 7] 取非负余数后的结果。
[samples]
## Note
在第一个测试用例中，第一行的数字为 #cf_span[3]、#cf_span[6]、#cf_span[9]、#cf_span[12] 和 #cf_span[15]。
Karen 执行的操作如下：
最终数字对 #cf_span[109 + 7] 取非负余数后仍为 #cf_span[36]，因此这是正确输出。
在第二个测试用例中，第一行的数字为 #cf_span[3]、#cf_span[7]、#cf_span[5] 和 #cf_span[2]。
Karen 执行的操作如下：
最终数字对 #cf_span[109 + 7] 取非负余数后为 #cf_span[109 + 6]，因此这是正确输出。
**Definitions**
Let $ n \in \mathbb{Z}^+ $ be the length of the initial sequence.
Let $ A = (a_1, a_2, \dots, a_n) $ be the initial sequence of integers.
Let $ f_k: \mathbb{Z}^k \to \mathbb{Z} $ denote the transformation applied to a sequence of length $ k $, defined recursively as:
- If $ k = 1 $, then $ f_1(x) = x $.
- If $ k > 1 $, then $ f_k(A) = f_{k-1}(B) $, where $ B = (b_1, b_2, \dots, b_{k-1}) $ and:
$$
b_i =
\begin{cases}
a_i + a_{i+1} & \text{if } i \text{ is odd and the current level starts with } +, \\
a_i - a_{i+1} & \text{if } i \text{ is even and the current level starts with } +, \\
a_i - a_{i+1} & \text{if } i \text{ is odd and the current level starts with } -, \\
a_i + a_{i+1} & \text{if } i \text{ is even and the current level starts with } -.
\end{cases}
$$
The operation alternates per level: level 1 starts with $ + $, level 2 starts with $ - $, level 3 with $ + $, etc.
Let $ M = 10^9 + 7 $.
**Constraints**
1. $ 1 \leq n \leq 200000 $
2. $ 1 \leq a_i \leq 10^9 $ for all $ i \in \{1, \dots, n\} $
**Objective**
Compute $ f_n(A) \mod M $.