Leha is planning his journey from Moscow to Saratov. He hates trains, so he has decided to get from one city to another by car.

The path from Moscow to Saratov can be represented as a straight line (well, it's not that straight in reality, but in this problem we will consider it to be straight), and the distance between Moscow and Saratov is n km. Let's say that Moscow is situated at the point with coordinate 0 km, and Saratov — at coordinate n km.

Driving for a long time may be really difficult. Formally, if Leha has already covered i kilometers since he stopped to have a rest, he considers the difficulty of covering (i + 1)-th kilometer as a_{i + 1}. It is guaranteed that for every i ∈ [1, n - 1] a_i ≤ a_{i + 1}. The difficulty of the journey is denoted as the sum of difficulties of each kilometer in the journey.

Fortunately, there may be some rest sites between Moscow and Saratov. Every integer point from 1 to n - 1 may contain a rest site. When Leha enters a rest site, he may have a rest, and the next kilometer will have difficulty a_1, the kilometer after it — difficulty a_2, and so on.

For example, if n = 5 and there is a rest site in coordinate 2, the difficulty of journey will be 2a_1 + 2a_2 + a_3: the first kilometer will have difficulty a_1, the second one — a_2, then Leha will have a rest, and the third kilometer will have difficulty a_1, the fourth — a_2, and the last one — a_3. Another example: if n = 7 and there are rest sites in coordinates 1 and 5, the difficulty of Leha's journey is 3a_1 + 2a_2 + a_3 + a_4.

Leha doesn't know which integer points contain rest sites. So he has to consider every possible situation. Obviously, there are 2^{n - 1} different distributions of rest sites (two distributions are different if there exists some point x such that it contains a rest site in exactly one of these distributions). Leha considers all these distributions to be equiprobable. He wants to calculate p — the expected value of difficulty of his journey.

Obviously, p ⋅ 2^{n - 1} is an integer number. You have to calculate it modulo 998244353.

Input

The first line contains one number n (1 ≤ n ≤ 10^6) — the distance from Moscow to Saratov.

The second line contains n integer numbers a_1, a_2, ..., a_n (1 ≤ a_1 ≤ a_2 ≤ ... ≤ a_n ≤ 10^6), where a_i is the difficulty of i-th kilometer after Leha has rested.

Output

Print one number — p ⋅ 2^{n - 1}, taken modulo 998244353.

Examples

Input

2
1 2


Output

5


Input

4
1 3 3 7


Output

60
import java.io.*;
import java.util.*;
/*
 * 	Heart beats fast
 * 		colors and promises
 * 			how to be brave
 * 				how can I love
 * 					when I am afraid to fall...  
 */
//read the question correctly (is y a vowel? what are the exact constraints?)
//look out for SPECIAL CASES (n=1?) and overflow (ll vs int?)
//always declare multidimensional arrays as [2][n] not [n][2]
//it can lead to upto 2-3x diff in runtime
//declare int/long tries with 16 array size due to object overhead :D
public class Main
{
	public static void main(String[]args) throws IOException
	{
		int n=ni();
		int[]a=new int[n+1];
		for(int i=n; i>0; i--)
			a[i]=ni();
		long ans=0;
		for(int i=1; i<=n; i++)
			ans=(ans+a[i]*(((powm(2,i-2+mod-1,mod))*(i+1))%mod))%mod;
		pr(ans);
		System.out.print(output);
	}
	///////////////////////////////////////////
	///////////////////////////////////////////
	///template from here
	static class pair
	{
		int a, b;
		pair(){}
		pair(int c,int d){a=c;b=d;}
	}
	static interface combiner
	{
		public int combine(int a, int b);
	}
	static final long mod=998244353;
	static final double eps=1e-9;
	static final long inf=100000000000000000L;
	static Reader in=new Reader();
	static StringBuilder output=new StringBuilder();
	static Random rn=new Random();
	static void reverse(int[]a){for(int i=0; i<a.length/2; i++){a[i]^=a[a.length-i-1];a[a.length-i-1]^=a[i];a[i]^=a[a.length-i-1];}}
	static int log2n(long a)
	{
		int te=0;
		while(a>0)
		{
			a>>=1;
			++te;
		}
		return te;
	}
	static class vectorl implements Iterable<Long>
	{
		long a[];
		int size;
		vectorl(){a=new long[10];size=0;}
		vectorl(int n){a=new long[n];size=0;}
		public void add(long b){if(++size==a.length)a=Arrays.copyOf(a, 2*size);a[size-1]=b;}
		public void sort(){Arrays.sort(a, 0, size);}
		public void sort(int l, int r){Arrays.sort(a, l, r);}
		@Override
		public Iterator<Long> iterator() {
			Iterator<Long> hola=new Iterator<Long>()
					{
				int cur=0;
						@Override
						public boolean hasNext() {
							return cur<size;
						}
						@Override
						public Long next() {
							return a[cur++];
						}				
					};
			return hola;
		}
	}
	static class vector implements Iterable<Integer>
	{
		int a[],size;
		vector(){a=new int[10];size=0;}
		vector(int n){a=new int[n];size=0;}
		public void add(int b){if(++size==a.length)a=Arrays.copyOf(a, 2*size);a[size-1]=b;}
		public void sort(){Arrays.sort(a, 0, size);}
		public void sort(int l, int r){Arrays.sort(a, l, r);}
		@Override
		public Iterator<Integer> iterator() {
			Iterator<Integer> hola=new Iterator<Integer>()
					{
				int cur=0;
						@Override
						public boolean hasNext() {
							return cur<size;
						}
						@Override
						public Integer next() {
							return a[cur++];
						}				
					};
			return hola;
		}
	}
	//output functions////////////////
	static void pr(Object a){output.append(a+"\n");}
	static void pr(){output.append("\n");}
	static void p(Object a){output.append(a);}
	static void pra(int[]a){for(int i:a)output.append(i+" ");output.append("\n");}
	static void pra(long[]a){for(long i:a)output.append(i+" ");output.append("\n");}
	static void pra(String[]a){for(String i:a)output.append(i+" ");output.append("\n");}
	static void pra(double[]a){for(double i:a)output.append(i+" ");output.append("\n");}
	static void sop(Object a){System.out.println(a);}
	static void flush(){System.out.print(output);output=new StringBuilder();}
	//////////////////////////////////
	//input functions/////////////////
	static int ni(){return Integer.parseInt(in.next());}
	static long nl(){return Long.parseLong(in.next());}
	static String ns(){return in.next();}
	static double nd(){return Double.parseDouble(in.next());}
	static int[] nia(int n){int a[]=new int[n];for(int i=0; i<n; i++)a[i]=ni();return a;}
	static int[] pnia(int n){int a[]=new int[n+1];for(int i=1; i<=n; i++)a[i]=ni();return a;}
	static long[] nla(int n){long a[]=new long[n];for(int i=0; i<n; i++)a[i]=nl();return a;}
	static String[] nsa(int n){String a[]=new String[n];for(int i=0; i<n; i++)a[i]=ns();return a;}
	static double[] nda(int n){double a[]=new double[n];for(int i=0; i<n; i++)a[i]=nd();return a;}
	//////////////////////////////////
	//some utility functions
	static void exit(){System.out.print(output);System.exit(0);}
	static int min(int... a){int min=a[0];for(int i:a)min=Math.min(min, i);return min;}
	static int max(int... a){int max=a[0];for(int i:a)max=Math.max(max, i);return max;}	
	static int gcd(int... a){int gcd=a[0];for(int i:a)gcd=gcd(gcd, i);return gcd;}	
	static long min(long... a){long min=a[0];for(long i:a)min=Math.min(min, i);return min;}
	static long max(long... a){long max=a[0];for(long i:a)max=Math.max(max, i);return max;}	
	static long gcd(long... a){long gcd=a[0];for(long i:a)gcd=gcd(gcd, i);return gcd;}	
	static String pr(String a, long b){String c="";while(b>0){if(b%2==1)c=c.concat(a);a=a.concat(a);b>>=1;}return c;}
	static long powm(long a, long b, long m){long an=1;long c=a;while(b>0){if(b%2==1)an=(an*c)%m;c=(c*c)%m;b>>=1;}return an;}
	static int gcd(int a, int b){if(b==0)return a;return gcd(b, a%b);}
	static long gcd(long a, long b){if(b==0)return a;return gcd(b, a%b);}
	static class Reader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;
        public Reader() {
            reader = new BufferedReader(new InputStreamReader(System.in), 32768);
            tokenizer = null;
        }
        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }
    }
}