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

<image>

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 ai (1 ≤ ai ≤ 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.

Examples

Input

5
3 6 9 12 15


Output

36


Input

4
3 7 5 2


Output

1000000006

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:

<image>

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:

<image>

The non-negative remainder after dividing the final number by 109 + 7 is 109 + 6, so this is the correct output.
import java.util.*;
import java.io.*;
import java.math.*;

/**
 *
 * @author superuser
 */
public class Test {

    static long mod = (long)1e9+7;
    static int N    = (int)1e6+5;
    ////////////////////////////////////////////////////////////
    static long[] a = new long[N];
    static long[] f = new long[N];
    static long[] t = new long[N];
    static long[] g = new long[N];
    static int n,m,count=0,ans=0;
    static void solve() {
        n = i();
        f[0] =1;
        for(int i=1;i<N;i++)
            f[i] = (f[i-1]*i)%mod;
        for(int i=1;i<=n;i++)
            a[i] = l();
        if(n%4==0)
        {
            for(int i=1;i<=n;i++)
            {
                if((i&1)==1)
                    t[i] = C(n/2-1,(i-1)/2);
                else
                    t[i] = -C(n/2-1,(i-1)/2);
            }
        }
        else if(n%4==1)
        {

            for(int i=1;i<=n;i++)
            {
                if((i&1)==1)
                    t[i] = C(n/2,i/2);
            }
        }
        else 
        {
    

            for(int i=1;i<=n;i++)
                t[i] = C(n/2-1,(i-1)/2);
            
            if(n%4==3)
            {
                g[1]=1;
                g[n]=-1;
                for(int i=2;i<n;i++)
                {
                    if((i&1)==1)
                    {
                        g[i] = t[i]-t[i-1];
                    }
                    else
                        g[i] = t[i] + t[i-1];
                }
                for(int i=1;i<=n;i++)
                    t[i] = g[i];
            }
        }
        
        long answer = 0;
        for(int i=1;i<=n;i++)
        {
            answer = (answer+mul(a[i],t[i]))%mod;
            answer %= mod;
        }
        
        out.println((answer+mod)%mod);
        out.close();
    }
    static long C(int n,int m)
    {
        if(n<m) return 0;
        long answ = mul(f[n],mul(powe(f[m],mod-2),powe(f[n-m],mod-2)));
       
        return answ;
    }
    static long powe(long x,long y)
    {
        if(y==0) return 1;
        long t = powe(x,y/2);
        if((y&1)==1) return mul(mul(t,t),x);
        return mul(t,t);
    }
    static InputReader sc = new InputReader(System.in);
    static PrintWriter out = new PrintWriter(System.out); 
    public static void main(String[] args) {

        new Thread(null,new Runnable() {
            @Override
            public void run() {
                try{
                    solve();
                }
                catch(Exception e){
                    e.printStackTrace();
                }
            }
        },"1",1<<26).start();
    }

    static class Pair implements Comparable<Pair>{

        int x,y,i;
        
        Pair (int x,int y,int i){
            this.x = x;
            this.y = y;
            this.i = i;
        }
            
        Pair (int x,int y){
            this.x = x;
            this.y = y;
        }
        
        public int compareTo(Pair o) {
                        return -Integer.compare(this.i,o.i);
        }

        public boolean equals(Object o) {
            if (o instanceof Pair) {
                Pair p = (Pair)o;
                return p.x == x && p.y==y;
            }
            return false;
        }

        @Override
        public String toString() {
            return x + " "+ y + " "+i;
        }
        
        public int hashCode() {
            return new Long(x).hashCode() * 31 + new Long(y).hashCode();
        }
    
    } 


    static class Merge {

        public static void sort(int inputArr[]) {
            int length = inputArr.length;
            doMergeSort(inputArr,0, length - 1);
        }

        private static void doMergeSort(int[] arr,int lowerIndex, int higherIndex) {        
            if (lowerIndex < higherIndex) {
                int middle = lowerIndex + (higherIndex - lowerIndex) / 2;
                doMergeSort(arr,lowerIndex, middle);
                doMergeSort(arr,middle + 1, higherIndex);
                mergeParts(arr,lowerIndex, middle, higherIndex);
            }
        }

        private static void mergeParts(int[]array,int lowerIndex, int middle, int higherIndex) {
            int[] temp=new int[higherIndex-lowerIndex+1];
            for (int i = lowerIndex; i <= higherIndex; i++) {
                temp[i-lowerIndex] = array[i];
            }
            int i = lowerIndex;
            int j = middle + 1;
            int k = lowerIndex;
            while (i <= middle && j <= higherIndex) {
                if (temp[i-lowerIndex] < temp[j-lowerIndex]) {
                    array[k] = temp[i-lowerIndex];
                    i++;
                } else {
                    array[k] = temp[j-lowerIndex];
                    j++;
                }
                k++;
            }
            while (i <= middle) {
                array[k] = temp[i-lowerIndex];
                k++;
                i++;
            }
            while(j<=higherIndex){
                array[k]=temp[j-lowerIndex];
                k++;
                j++;
            }
        }

    }

    static long add(long a,long b){
        long x=(a+b);
        while(x>=mod) x-=mod;
        return x;
    }

    static long sub(long a,long b){
        long x=(a-b);
        while(x<0) x+=mod;
        return x;
    }

    static long mul(long a,long b){
        a%=mod;
        b%=mod;
        long x=(a*b);
        return x%mod;
    }


    static boolean isPal(String s){
        for(int i=0, j=s.length()-1;i<=j;i++,j--){
                if(s.charAt(i)!=s.charAt(j)) return false;
        }
        return true;
    }
    static String rev(String s){
                StringBuilder sb=new StringBuilder(s);
                sb.reverse();
                return sb.toString();
    }

    static long gcd(long x,long y){
        if(y==0)
                return x;
        else
                return gcd(y,x%y);
    }

    static int gcd(int x,int y){
        if(y==0)
                return x;
        else 
                return gcd(y,x%y);
    }

    static long gcdExtended(long a,long b,long[] x){

        if(a==0){
            x[0]=0;
            x[1]=1;
            return b;
        }
        long[] y=new long[2];
        long gcd=gcdExtended(b%a, a, y);

        x[0]=y[1]-(b/a)*y[0];
        x[1]=y[0];

        return gcd;
    }


    static long mulmod(long  a,long b,long m) {
        if (m <= 1000000009) return a * b % m;

        long res = 0;
        while (a > 0) {
            if ((a&1)!=0) {
                res += b;
                if (res >= m) res -= m;
            }
            a >>= 1;
            b <<= 1;
            if (b >= m) b -= m;
        }
        return res;
    }

    static int abs(int a,int b){
        return (int)Math.abs(a-b);
    }

    public static long abs(long a,long b){
        return (long)Math.abs(a-b);
    }

    static int max(int a,int b){
        if(a>b)
                return a;
        else
                return b;
    }

    static int min(int a,int b){
        if(a>b)
                return b;
        else 
                return a;
    }

    static long max(long a,long b){
        if(a>b)
                return a;
        else
                return b;
    }

    static long min(long a,long b){
        if(a>b)
                return b;
        else 
                return a;
    }

    static long pow(long n,long p,long m){
         long  result = 1;
          if(p==0)
            return 1;

        while(p!=0)
        {
            if(p%2==1)
                result *= n;
            if(result>=m)
            result%=m;
            p >>=1;
            n*=n;
            if(n>=m)
            n%=m;
        }
        return result;
    }

    static long pow(long n,long p){
        long  result = 1;
          if(p==0)
            return 1;

        while(p!=0)
        {
            if(p%2==1)
                result *= n;        
            p >>=1;
            n*=n;       
        }
        return result;
    }

    static void debug(Object... o) {
            System.out.println(Arrays.deepToString(o));
    }

    static class InputReader {

        private final InputStream stream;
        private final byte[] buf = new byte[8192];
        private int curChar, snumChars;
        private SpaceCharFilter filter;

        public InputReader(InputStream stream) {
                this.stream = stream;
        }

        public int snext() {
                if (snumChars == -1)
                        throw new InputMismatchException();
                if (curChar >= snumChars) {
                        curChar = 0;
                        try {
                                snumChars = stream.read(buf);
                        } catch (IOException e) {
                                throw new InputMismatchException();
                        }
                        if (snumChars <= 0)
                                return -1;
                }
                return buf[curChar++];
        }

        public int nextInt() {
                int c = snext();
                while (isSpaceChar(c)) {
                        c = snext();
                }
                int sgn = 1;
                if (c == '-') {
                        sgn = -1;
                        c = snext();
                }
                int res = 0;
                do {
                        if (c < '0' || c > '9')
                                throw new InputMismatchException();
                        res *= 10;
                        res += c - '0';
                        c = snext();
                } while (!isSpaceChar(c));
                return res * sgn;
        }

        public long nextLong() {
                int c = snext();
                while (isSpaceChar(c)) {
                        c = snext();
                }
                int sgn = 1;
                if (c == '-') {
                        sgn = -1;
                        c = snext();
                }
                long res = 0;
                do {
                        if (c < '0' || c > '9')
                                throw new InputMismatchException();
                        res *= 10;
                        res += c - '0';
                        c = snext();
                } while (!isSpaceChar(c));
                return res * sgn;
        }

        public int[] nextIntArray(int n) {
                int a[] = new int[n];
                for (int i = 0; i < n; i++) {
                        a[i] = nextInt();
                }
                return a;
        }

        public long[] nextLongArray(int n) {
                long a[] = new long[n];
                for (int i = 0; i < n; i++) {
                        a[i] = nextLong();
                }
                return a;
        }

        
        public String nextLine() {
                int c = snext();
                while (isSpaceChar(c))
                        c = snext();
                StringBuilder res = new StringBuilder();
                do {
                        res.appendCodePoint(c);
                        c = snext();
                } while (!isEndOfLine(c));
                return res.toString();
        }

        public boolean isSpaceChar(int c) {
                if (filter != null)
                        return filter.isSpaceChar(c);
                return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        private boolean isEndOfLine(int c) {
                return c == '\n' || c == '\r' || c == -1;
        }

        public interface SpaceCharFilter {
                public boolean isSpaceChar(int ch);
        }

    }
    static int i()
    {
        return sc.nextInt();
    }
    static long l(){
        return sc.nextLong();
    }
    static int[] iarr(int n)
    {
        return sc.nextIntArray(n);
    }
    static long[] larr(int n)
    {
        return sc.nextLongArray(n);
    }
    static String s(){
        return sc.nextLine();
    }
} 