由 个整数构成的数组 ，我们有如下操作： 你必须在这些整数之间交替写下加减符号，例如假设数组初始值 ，交替写下加减符号变为 ； 此时会生成第二行数组 ，即 ；随后，再次交替写下加减符号变为 （由于上一行末尾是 + ，所以这一行的开头是 - ）； 此时会生成第三行数组 ，继续重复上述操作； 直到最后只剩下唯一一个数字时，中止操作，在上方的样例中，最后剩下的数字为 。 现在，你需要独立求出给定的数组剩下的最后一个值是多少。

输入描述:

第一行输入一个整数  代表数组中的元素数量。第二行输入  个整数  代表数组元素。

输出描述:

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