Problem: Problem

Define a function $ f $ that starts with $ 1 $ and takes a sequence of finite lengths as an argument as follows.

$ \ displaystyle f (\\ {a_1, a_2, \ ldots, a_n \\}) = \ sum_ {i = 1} ^ n {a_i} ^ i $

Given a sequence of length $ N $, $ X = \\ {x_1, x_2, \ ldots, x_N \\} $, $ f (X) for all subsequences $ X'$ except empty columns. ') Find $ and output the sum of them divided by $ 998244353 $. However, the subsequence subsequences shall be renumbered starting from $ 1 $ while maintaining the relative order in the original sequence. Also, even if two subsequences are the same as columns, if they are taken out at different positions, they shall be counted separately.

Constraints

The input satisfies the following conditions.

* $ 1 \ leq N \ leq 10 ^ 6 $
* $ 1 \ leq x_i \ leq 10 ^ 6 $
* All inputs are integers

Input

The input is given in the following format.


$ N $
$ x_1 $ $ \ ldots $ $ x_N $


The first line is given the length $ N $. In the second row, the elements of the sequence $ X $ are given, separated by blanks.

Output

Find $ f (X') $ for all subsequences $ X'$ except empty columns, and divide the sum by $ 998244353 $ to output the remainder.

Examples

Input

3
1 2 3


Output

64


Input

5
100 200 300 400 500


Output

935740429

Solution (in CPP):

Solution:
/* monkukui 競技プログラミング用のテンプレート  (ここから) */
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <functional>
#include <bitset>

using namespace std;
using lint = long long int;
using ll = long long int;
using lnt = long long int;
using graph = vector<vector<long long int>>;
using wgraph = vector<vector<pair<long long int, long long int>>>;
long long int INF = 1001001001001001LL;
long long int MOD = 998244353LL;
double PI = 3.1415926535897932;
long long int di[] = {-1, 0, 1, 0, -1, 1, 1, -1};
long long int dj[] = {0, 1, 0, -1, 1, 1, -1, -1};

template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}
inline void yes(){ cout << "yes" << endl; }
inline void Yes(){ cout << "Yes" << endl; }
inline void YES(){ cout << "YES" << endl; }
inline void no(){ cout << "no" << endl; }
inline void No(){ cout << "No" << endl; }
inline void NO(){ cout << "NO" << endl; }
inline void possible(){ cout << "possible" << endl; }
inline void Possible(){ cout << "Possible" << endl; }
inline void POSSIBLE(){ cout << "POSSIBLE" << endl; }
inline void impossible(){ cout << "impossible" << endl; }
inline void Impossible(){ cout << "Impossible" << endl; }
inline void IMPOSSIBLE(){ cout << "IMPOSSIBLE" << endl; }

#define rep(i,n) for(long long int i = 0; i < (n); i++)
#define rrep(i,n) for(long long int i = 1; i <= (n); i++)
#define drep(i,n) for(long long int i = (n)-1; i >= 0; i--)
#define srep(i,s,t) for(long long int i = s; i < t; i++)
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define pb push_back

/* monkukui 競技プログラミング用のテンプレート (ここまで)*/


const int MAXN = 1001024;

// a, b の最大公約数を返す O( log max(a, b) )
int gcd(int a, int b) {
    if(b == 0) return a;
    return gcd(b, a % b);
}

// ax + by = 1 となるような (x, y) と gcd(a, b) を返す. gcd(a, b) = 1 の時、解が存在する.
int extgcd(int a, int b, int &x, int &y){
    int d = a;
    if(b != 0){
        d = extgcd(b, a, y, x);
        y -= (a / b) * x;
    }else{
        x = 1;
        y = 0;
    }
    return d;
}


// 区間 [a, b) に存在する素数の個数を返す関数

int prime[MAXN];        // [a,b) の素数のうち i 番目の素数
bool is_prime[MAXN];    // 整数 i が素数であるかどうか
bool is_prime_ab[MAXN]; // 整数 i+a が素数であるかどうか

int sieve(int n) {
    int res = 0;
    fill(is_prime, is_prime + MAXN, true);
    is_prime[0] = is_prime[1] = false; // 0 と 1 は素数ではない。
    for(int i = 2; i <= n; ++i) {
        if(!is_prime[i]) continue;
        prime[res++] = i;
        for(int j = 2 * i; j <= n; j += i) is_prime[j] = false; // 素数 i の倍数は素数ではない (ふるい(篩)にかける)
    }
    return res;
}

/*
int segment_sieve(int a, int b){
    fill(is_prime, is_prime + MAXN, true);
    fill(is_prime_ab, is_prime_ab + MAXN, true);
    for(int i = 2; i * i <= b - 1; i++) {
        if(!is_prime[i]) continue;
        for(int j = 2 * i; j * j <= b - 1; j += i) is_prime[j] = false; // 素数 i で篩にかける
        for(int j = a - a % i; j < b; j += i) {
            if(j < a) continue;
            if(is_prime_ab[j-a]) is_prime_ab[j-a] = false; // 素数 i で篩にかける
        }
    }

    int res = 0;
    for(int i = a; i < b; i++) if(is_prime_ab[i - a]) prime[res++] = i;
    return res;
}
*/

// ある整数の約数列挙
vector<int> divisors(int n) {
    vector<int> res;
    for(int i = 1; i*i <= n; ++i) {
        if(n % i != 0) continue;
        res.push_back(i);
        if(n/i == i) continue; // 上の行で追加済み。
        res.push_back(n/i);
    }
    return res;
}


// 素因数分解
map<int, int> prime_factors(int n) {
    map<int, int> res;
    if(n == 1) { // n=1 の素因数分解は n^1
        res[n] = 1;
        return res;
    }
    for(int i = 2, _n = n; i*i <= _n; ++i) {
        while(n % i == 0) {
            ++res[i]; // 素数i^{res[i]}
            n /= i;
        }
    }
    if(n != 1) res[n] = 1;
    return res;
}


// 繰り返し 2 乗法
lint modpow(lint a, lint n, lint MOD) {
    int res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % MOD;
        a = a * a % MOD;
        n >>= 1;
    }
    return res;
}


// 逆元を求める. a と m は互いに素であることが要請される.
int modinv(int a, int m) {
    int b = m, u = 1, v = 0;
    while(b){
        int t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m; 
    if (u < 0) u += m;
    return u;
}

long long fac[MAXN], finv[MAXN], inv[MAXN];

// 前処理 O(n)
void comb_init(){
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for(int i = 2; i < MAXN; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

// 二項係数計算 O(1)
int COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}




int main(){
  
  int n; cin >> n;
  vector<lint> a(n);
  for(int i = 0; i < n; i++) cin >> a[i];
  lint ans = 0;
  for(lint i = 1; i <= n; i++) {
    lint add = 1LL;
    add *= modpow(2, n - i, MOD);
    add %= MOD;
    add *= a[i - 1];
    add %= MOD;
    add *= modpow(1 + a[i - 1], i - 1, MOD);
    add %= MOD;
    ans += add;
    ans %= MOD;
  }

  cout << ans << endl;

  return 0;
}