题目内容

由$n$个整数构成的数组{$a_1,a_2,...,a_n$}，我们有如下操作:

• 你必须在这些整数之间交替写下加减符号，例如假设数组初始值 {$1,2,3,4$}，交替写下加减符号变为$1+2-3+4$;

• 此时会生成第二行数组{$1+2,2-3,3+4$}，即{$3,-1,7$};随后，再次交替写下加减符号变为$3-(-1)+7$(由于上一行末尾是$+$，所以这一行的开头是$-$);

• 此时会生成第三行数组{$4,6$}，继续重复上述操作;

• 直到最后只剩下唯一一个数字时，中止操作，在上方的样例中，最后剩下的数字为$-2$。

  现在，你需要独立求出给定的数组剩下的最后一个值是多少。

输入描述

第一行输入一个整数$n$($1≤n≤10^5$)代表数组中的元素数量。

第二行输入$n$个整数$a_1,a_2,...,a_n$ ($1≤a_i≤10^9$)代表数组元素。

输出描述

在一行上输出一个整数，表示剩下的最后一个值。由于答案可能很大，只需要输出答案对$10^9+7$取模的结果。

样例1

输入

4
1 2 3 4

输出

1000000005

说明

该样例已在题面中说明，注意，负数也需要取模。