题目描述

可怜刚刚到达学校，并且她今天有一场数学考试。

这场考试是关于基本的加减法的。不幸的是，老师们都忙于给 Codeforces rounds 出测试，以至于没有时间出一个实际的考试。所以，他们仅在这场考试中出了一道包含所有分数的题。

有 $n$ 个整数被写在一行上。可怜必须对相邻的两个整数交替进行加减法，并把结果写在下一行。她需要重复这个过程直到只剩下一个整数。第一个操作应当是加法。

注意，如果在上一行她以加法结束，那么下一行她应当以减法开始，反之亦然。

老师们将只关心最后一个整数，如果它正确，可怜将得到所有分数，否则她这场考试将爆零。

可怜在这场考试发挥的很好，但是她害怕会在某处犯错误，并导致她的最终答案错误。如果按这个过程下来，她最后一行应写什么数？

因为这个数可能非常大，仅需输出一个对 $10^9+7$ 取模后的非负整数的结果。

输入格式

第一行包含一个整数 $n$（$1\leq n\leq200000$），表示写在第一行的数的个数。

下一行包含 $n$ 个整数。具体来说，第 $i$ 个数为 $a_i$（$1\leq a_i\leq10^9$），表示在第一行写下的第 $i$ 个数。

输出格式

输出一行一个整数，表示在这个过程后，最后一行写下的数。

因为这个数可能非常大，仅需输出一个对 $10^9+7$ 取模后的非负整数的结果。

5
3 6 9 12 15

36

4
3 7 5 2

1000000006