#include using namespace std; #define REP(i,a,b) for(i=a;i'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);} void reader(ll *x){int k,m=0;*x=0;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){*x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||k>'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);} void reader(double *x){scanf("%lf",x);} int reader(char c[]){int i,s=0;for(;;){mygc(i);if(i!=' '&&i!='\n'&&i!='\r'&&i!='\t'&&i!=EOF) break;}c[s++]=i;for(;;){mygc(i);if(i==' '||i=='\n'||i=='\r'||i=='\t'||i==EOF) break;c[s++]=i;}c[s]='\0';return s;} template void reader(T *x, S *y){reader(x);reader(y);} template void reader(T *x, S *y, U *z){reader(x);reader(y);reader(z);} template void reader(T *x, S *y, U *z, V *w){reader(x);reader(y);reader(z);reader(w);} void writer(int x, char c){int s=0,m=0;char f[10];if(x<0)m=1,x=-x;while(x)f[s++]=x%10,x/=10;if(!s)f[s++]=0;if(m)mypc('-');while(s--)mypc(f[s]+'0');mypc(c);} void writer(ll x, char c){int s=0,m=0;char f[20];if(x<0)m=1,x=-x;while(x)f[s++]=x%10,x/=10;if(!s)f[s++]=0;if(m)mypc('-');while(s--)mypc(f[s]+'0');mypc(c);} void writer(double x, char c){printf("%.15f",x);mypc(c);} void writer(const char c[]){int i;for(i=0;c[i]!='\0';i++)mypc(c[i]);} void writer(const char x[], char c){int i;for(i=0;x[i]!='\0';i++)mypc(x[i]);mypc(c);} template void writerLn(T x){writer(x,'\n');} template void writerLn(T x, S y){writer(x,' ');writer(y,'\n');} template void writerLn(T x, S y, U z){writer(x,' ');writer(y,' ');writer(z,'\n');} template void writerArr(T x[], int n){int i;if(!n){mypc('\n');return;}rep(i,n-1)writer(x[i],' ');writer(x[n-1],'\n');} char memarr[77000000]; void *mem = memarr; #define MD 1000000007 int get_inv(ll a, int md){ll t=a,s=md,u=1,v=0,e;while(s){e=t/s;t-=e*s;u-=e*v;swap(t,s);swap(u,v);}if(u<0)u+=md;return u;} struct mint{ static unsigned md, W, R, Rinv, mdninv, RR; unsigned val; mint(){}mint(int a){val=mulR(a);}mint(unsigned a){val=mulR(a);}mint(ll a){val=mulR(a);}mint(ull a){val=mulR(a);} void setmod(unsigned m){int i;unsigned t;W=32;md=m;R=(1ULL<>W);if(t>=md)t-=md;return t;}unsigned reduce(ull T){unsigned m=(unsigned)T*mdninv;unsigned t=(unsigned)((T+(ull)m*md)>>W);if(t>=md)t-=md;return t;} unsigned get(){return reduce(val);} mint&operator+=(mint a){val+=a.val;if(val>=md)val-=md;return*this;}mint&operator-=(mint a){if(val>=1;a*=a;}return r;} bool operator==(int a){return get()==a;} bool operator!=(int a){return get()!=a;} }; unsigned mint::md, mint::W, mint::R, mint::Rinv, mint::mdninv, mint::RR; mint operator+(int a, mint b){return mint(a)+=b;}mint operator-(int a, mint b){return mint(a)-=b;}mint operator*(int a, mint b){return mint(a)*=b;}mint operator/(int a, mint b){return mint(a)/=b;} mint operator+(ll a, mint b){return mint(a)+=b;}mint operator-(ll a, mint b){return mint(a)-=b;}mint operator*(ll a, mint b){return mint(a)*=b;}mint operator/(ll a, mint b){return mint(a)/=b;} mint mval[10000], minv[10000]; void mint_init(int md=MD, mint val[]=mval, int vals=10000, mint inv[]=minv, int invs=10000){int i;val[0].setmod(md);val[0].val=0;REP(i,1,vals){val[i].val=val[i-1].val+mint::R;if(val[i].val >=md)val[i].val-=md;}inv[1].val=1;REP(i,2,invs){inv[i].val=md-((ll)(md/i)*inv[md%i].val%md);}REP(i,1,invs)inv[i].val=(ull)inv[i].val*mint::R%md;} template struct lazySegtreeSumWithCoef_AddOnly{ int N, logN; T *data, *addval; S *coef, *coefsum; void malloc(int maxN){int i;for(i=1;i2)addval[a*2]+=addval[a],addval[a*2+1]+=addval[a];data[a*2]+=(coefsum[(st+ed)/2]-coefsum[st])*addval[a];data[a*2+1]+=(coefsum[ed]-coefsum[(st+ed)/2])*addval[a];addval[a]=0;}} inline void push(int a){int i,s=0,e=N;for(i=logN;i;i--){push_one(a>>i,s,e);if((a>>(i-1))&1)s=(s+e)/2;else e=(s+e)/2;}} inline void build(int a){int s=a-N,e=a-N+1;while(a>1){if(a%2)s-=e-s;else e+=e-s;a/=2;data[a]=data[a*2]+data[a*2+1];if(addval[a]!=0)data[a]+=addval[a]*(coefsum[e]-coefsum[s]);}} inline void add(int a, int b, T val){int c,d,s=a,t=b,sz=1;if(a>=b)return;c=(a+=N);d=(b+=N);push(a);push(b-1);if(a%2){data[a]+=val*(coefsum[s+sz]-coefsum[s]);a++;s+=sz;}if(b%2){b--;data[b]+=val*(coefsum[t]-coefsum[t-sz]);t-=sz;}a/=2;b/=2;while(a=0;j--){i=q[j];sz[i]=1;rep(k,es[i])sz[i]+=sz[edge[i][k]];}rep(i,N)group[i]=-1;groupNum=0;rep(j,N){i=q[j];if(group[i]>=0)continue;group[i]=groupNum++;groupind[i]=0;for(;;){m=-1;rep(k,es[i]){if(group[edge[i][k]]!=-1)continue;if(m==-1)m=k;else if(sz[edge[i][k]]>sz[edge[i][m]])m=k;}if(m==-1)break;group[edge[i][m]]=group[i];groupind[edge[i][m]]=groupind[i]+1;i=edge[i][m];}}groupSize=(int*)mem;groupUpNode=groupSize+groupNum;groupDepth=groupUpNode+groupNum;rep(i,groupNum)groupSize[i]=0;rep(i,N)groupSize[group[i]]++;groupNode=(int**)(groupDepth+groupNum);groupNode[0]=(int*)(groupNode+groupNum);REP(i,1,groupNum)groupNode[i]=groupNode[i-1]+groupSize[i-1];mem=groupNode[groupNum-1]+groupSize[groupNum-1];rep(i,N)groupNode[group[i]][groupind[i]]=i;rep(i,groupNum)groupDepth[i]=-1;groupUpNode[0]=-1;groupDepth[0]=0;rep(x,groupNum)rep(y,groupSize[x]){i=groupNode[x][y];rep(j,es[i]){k=edge[i][j];if(x!=group[k]&&groupDepth[group[k]]==-1)groupUpNode[group[k]]=i,groupDepth[group[k]]=groupDepth[x]+1;}}return mem;} }; template struct HLD_Node_LazySegtreeSumWithCoef_AddOnly{ HLD *hld; lazySegtreeSumWithCoef_AddOnly*seg; void* init(HLD *hld__, T initval[], S coef[], void *mem){int i,j;hld=hld__;seg=(lazySegtreeSumWithCoef_AddOnly*)mem;mem=seg+hld->groupNum;rep(i,hld->groupNum){mem=seg[i].malloc(hld->groupSize[i], mem);seg[i].setN(hld->groupSize[i]);if(initval!=NULL)rep(j,hld->groupSize[i])seg[i][j]=initval[hld->groupNode[i][j]];if(coef!=NULL)rep(j,hld->groupSize[i])seg[i].coef[j]=coef[hld->groupNode[i][j]];seg[i].build();}return mem;} void add(int u, int v, T val){int X=hld->group[u],Y=hld->group[v],Z,W;while(X!=Y){if(hld->groupDepth[X]groupDepth[Y])swap(u,v),swap(X,Y);seg[X].add(0,hld->groupind[u]+1,val);u=hld->groupUpNode[X];X=hld->group[u];}Z=hld->groupind[u];W=hld->groupind[v];seg[X].add(min(Z,W),max(Z,W)+1,val);} T getSum(int u, int v){T res=0;int X=hld->group[u],Y=hld->group[v],Z,W;while(X!=Y){if(hld->groupDepth[X]groupDepth[Y])swap(u,v),swap(X,Y);res+=seg[X].getSum(0,hld->groupind[u]+1);u=hld->groupUpNode[X];X=hld->group[u];}Z=hld->groupind[u];W=hld->groupind[v];res+=seg[X].getSum(min(Z,W),max(Z,W)+1);return res;} }; void* setUndirectEdge(int N, int M, int A[], int B[], int **es, int ***edge, void *workMemory){int i;*es=(int*)workMemory;*edge=(int**)((*es)+N);(*edge)[0]=(int*)((*edge)+N);rep(i,N)(*es)[i]=0;rep(i,M)(*es)[A[i]]++,(*es)[B[i]]++;REP(i,1,N)(*edge)[i]=(*edge)[i-1]+(*es)[i-1];workMemory=(void*)((*edge)[N-1]+(*es)[N-1]);rep(i,N)(*es)[i]=0;rep(i,M)(*edge)[A[i]][(*es)[A[i]]++]=B[i],(*edge)[B[i]][(*es)[B[i]]++]=A[i];return workMemory;} void getDist(int N, int root, int *es, int **edge, int dist[], void *mem){int i,j,k,*q,s,z;q=(int*)mem;rep(i,N)dist[i]=-1;dist[root]=0;s=0;z=1;q[0]=root;while(z){i=q[s++];z--;rep(j,es[i]){k=edge[i][j];if(dist[k]>=0)continue;dist[k]=dist[i]+1;q[s+z++]=k;}}} int N, Q; int A[300000], B[300000], S[300000], C[300000]; int T, X, Y, Z; int *es, **edge; mint SS[300000], CC[300000]; int main(){ int i, j, k; HLD hld; HLD_Node_LazySegtreeSumWithCoef_AddOnly seg; mint res; mint_init(); reader(&N); assert(2 <= N && N <= 200000); rep(i,N) reader(S+i), assert(0<=S[i] && S[i]