#include<bits/stdc++.h> #define pii pair<int,int> #define fi first #define se second #define mk make_pair #define ll long long using namespace std; const int N=3e4+10,mod=998244353; const int Mod[]={998244353,998244352,402653184,134217728,67108864,33554432,16777216,8388608,4194304,2097152,1048576,524288,262144,131072,65536,32768,16384,8192,4096,2048,1024,512,256,128,64,32,16,8,4,2,1,0}; const int inf=1e9+10; unsigned int pw[N][9][17],pw2[N][5][257]; int qp(int a,int b){ int x=1; for(;b;b>>=1,a=1ll*a*a%mod)if(b&1)x=1ll*x*a%mod; return x; } int qp(int ps,int b,int id){ if(id<=3){ int x=1; for(int i=0;i<=7;i++) x=1ll*x*pw[ps][i][b&15]%Mod[id],b>>=4; //for(;b;b>>=1,a=1ll*a*a%Mod[id])if(b&1)x=1ll*x*a%Mod[id]; return x; }else{ unsigned int x=1; for(int i=0;i<=7;i++) x*=pw[ps][i][b&15],b>>=4; return x&(Mod[id]-1); } } int QP(int id,int b){ int x=1; for(int i=0;i<=3;i++) x=min((ll)inf,1ll*x*pw2[id][i][b&255]),b>>=8; return x; } int n,a[N],p2[N]; pii calc(int l,int r,int id){ if(l==r) return mk(a[l]%Mod[id],a[l]); if(Mod[id]==1){ pii res=calc(l+1,r,id); return mk(0,QP(l,res.se)); }else{ pii res=calc(l+1,r,id+1); if(res.se>Mod[id+1]) res.fi+=Mod[id+1]; return mk(qp(l,res.fi,id),QP(l,res.se)); } } const int B=40; int main(){ //freopen("boom.in","r",stdin); //freopen("boom.out","w",stdout); cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; p2[0]=1; for(int i=1;i<=n;i++) p2[i]=2ll*p2[i-1]%mod; for(int i=1;i<=n;i++){ for(int j=0;j<=3;j++){ pw2[i][j][0]=1; if(!j) pw2[i][j][1]=a[i]; else pw2[i][j][1]=pw2[i][j-1][256]; for(int k=2;k<=256;k++) pw2[i][j][k]=min((ll)inf,1ll*pw2[i][j][k-1]*pw2[i][j][1]); } } map<int,int> mp; int ans=0; for(int i=n;i>=1;i--){ int res=0; for(int j=0;Mod[j]>=1&&i+j<=n;j++){ for(int x=0;x<=7;x++){ pw[i+j][x][0]=1; if(!x) pw[i+j][x][1]=a[i+j];else pw[i+j][x][1]=pw[i+j][x-1][16]; if(j<=3){ for(int y=2;y<=16;y++) pw[i+j][x][y]=1ll*pw[i+j][x][y-1]*pw[i+j][x][1]%Mod[j]; }else{ for(int y=2;y<=16;y++) pw[i+j][x][y]=pw[i+j][x][y-1]*pw[i+j][x][1]; } } } for(int j=0;j<=B&&i+j<=n;j++){ pii w=calc(i,i+j,0); if(j!=B) res=(res+1ll*w.fi*p2[max(n-(i+j)-1,0)])%mod; else res=(res+1ll*w.fi*p2[n-(i+j)])%mod; } /*res=0; for(int j=0;i+j<=n;j++){ pii w=calc(i,i+j,0); cout<<i<<' '<<i+j<<' '<<w.fi<<endl; res=(res+1ll*w.fi*p2[max(n-(i+j)-1,0)])%mod; }*/ ans=(ans+1ll*res*p2[max(i-2,0)])%mod; //cout<<i<<' '<<res<<endl; }cout<<ans<<'\n'; return 0; }