#include<map>
#include<queue>
#include<cmath>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define MAXN 100005
#define ENDL putchar('\n')
#define LL long long
#define DB double
#define lowbit(x) ((-x) & (x))
LL read() {
	LL f = 1,x = 0;char s = getchar();
	while(s < '0' || s > '9') {if(s=='-')f = -f;s = getchar();}
	while(s >= '0' && s <= '9') {x=x*10+(s-'0');s = getchar();}
	return f * x;
}
const int MOD = 1000000007;
int n,m,i,j,s,o,k;
int a[MAXN];
int dp[MAXN];
int main() {
	n = read();
	int sum = 0,sum2 = 0;
	dp[0] = 1; dp[1] = 1;
	for(int i = 2;i <= n;i ++) {
		dp[i] = (dp[i-1]+dp[i-2]) % MOD;
	}
	for(int i = 1;i <= n;i ++) {
		a[i] = read();
		(sum += a[i]) %= MOD;
		if(i > 1) {
			(sum2 += dp[i-2] *1ll* dp[n-i] % MOD *2ll* a[i] % MOD) %= MOD;
		}
	}
	printf("%lld\n",(sum*1ll*dp[n]%MOD+MOD-sum2) % MOD);
	return 0;
}
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define REP(i,m,n) for(int i=(m);i<(n);i++)
#define rep(i,n) REP(i,0,n)
#define pb push_back
#define all(a) a.begin(),a.end()
#define rall(c) (c).rbegin(),(c).rend()
#define mp make_pair
#define endl '\n'
#define vec vector<ll>
#define mat vector<vector<ll> >
#define fi first
#define se second
#define double long double
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pll;
//typedef long double ld;
typedef complex<double> Complex;
const ll INF=1e9+7;
const ll MOD=998244353;
const ll inf=INF*INF;
const ll mod=INF;
const ll MAX=100010;

signed main(){
    ll n;cin>>n;
    ll ans=n;
    ll k=1;
    ll cnt=0;
    while(n>=k){
        ans=min(ans,n/k+cnt+n%k);
        cnt++;
        k*=2LL;
    }
    cout<<ans<<endl;
}