#include<bits/stdc++.h> #define double long double using namespace std; int n,m,k;int a[1000050]; int mod=1e9+7; int ans=0; int b[100050]; int val[1200050]; #define ls p*2 #define rs p*2+1 #define mid (l+r)/2 int tag[1200050]; inline void pu(int p){ val[p]=(val[ls]+val[rs])%mod; }inline void pd(int p){ val[ls]=1ll*tag[p]*k%mod*val[ls]%mod; val[rs]=1ll*tag[p]*k%mod*val[rs]%mod; //if(val[ls]<=1e-10) val[ls]=0; //if(val[rs]<=1e-10) val[rs]=0; tag[ls]=1ll*tag[p]*tag[ls]%mod; tag[rs]=1ll*tag[p]*tag[rs]%mod; tag[p]=1; }inline void bd(int p,int l,int r){ tag[p]=1; if(l==r) {val[p]=0;return ;} bd(ls,l,mid); bd(rs,mid+1,r); pu(p); }inline void upd1(int p,int l,int r,int x,int v){ //if(l==r&&l==1) cout<<val[p]<<' '; if(l==r&&l==x){val[p]+=v;return ;} pd(p); if(x<=mid) upd1(ls,l,mid,x,v); else upd1(rs,mid+1,r,x,v); pu(p); }inline void upd2(int p,int l,int r,int pl,int pr){ if(pl<=l&&r<=pr){ val[p]=1ll*val[p]*k%mod; //if(val[p]<=1e-10) val[p]=0; tag[p]*=1ll*tag[p]*k%mod; return ; }pd(p); if(pl<=mid) upd2(ls,l,mid,pl,pr); if(pr>mid) upd2(rs,mid+1,r,pl,pr); pu(p); cout<<val[p]<<' '; }inline int qu(int p,int l,int r,int pl,int pr){ if(pl<=l&&r<=pr) return val[p]; pd(p); long long res=0; if(pl<=mid) res+=qu(ls,l,mid,pl,pr); if(pr>mid) res+=qu(rs,mid+1,r,pl,pr); return res%mod; } int powk[300050]; struct SEG{ int siz[1200050],jp8[1200050]; struct seg{ int s,j; }; inline void pushup(int p){ jp8[p]=(jp8[ls]*powk[siz[rs]]%mod+jp8[rs])%mod; } inline void build(int p,int l,int r){ if(l==r){ siz[p]=0,jp8[p]=1; return ; } build(ls,l,mid); build(rs,mid+1,r); pushup(p); }inline void upd(int p,int l,int r,int x){ if(l==r&&l==x){jp8[p]=jp8[p]*k%mod;siz[p]++;return ;} if(x<=mid) upd(ls,l,mid,x); else upd(rs,mid+1,r,x); pushup(p); }seg query(int p,int l,int r,int pl,int pr){ if(pl<=l&&r<=pr) return (seg){siz[p],jp8[p]}; if(pr<=mid) return query(ls,l,mid,pl,pr); if(pl>mid) return query(rs,mid+1,r,pl,pr); seg L=query(ls,l,mid,pl,pr); seg R=query(rs,mid+1,r,pl,pr); return (seg){L.s+R.s,(L.j*powk[R.s]%mod+R.j)%mod}; }int Q(int p,int l,int r,int pl,int pr){ return query(p,l,r,pl,pr).j; } }SEGTREE; int pre[300050],suf[300050]; struct nd{ int id,vl; };bool cmp(nd a,nd b){ return (a.vl==b.vl)?(a.id<b.id):(a.vl<b.vl); } void slv3(){ bd(1,1,3e5+1); nd d[300050]; int gc[300050]; for(int i=1;i<=n;i++) d[i]=(nd){i,a[i]}; sort(d+1,d+n+1,cmp); SEGTREE.build(1,1,n); for(int i=1;i<=n;i++){ SEGTREE.upd(1,1,n,d[i].id); gc[d[i].id]=SEGTREE.Q(1,1,n,1,d[i].id)*d[i].vl%mod; } for(int i=1;i<=n;i++){ upd2(1,1,3e5+1,a[i],3e5+1); cout<<qu(1,1,3e5+1,1,1)<<' '; upd1(1,1,3e5+1,a[i],gc[i]); pre[i]+=qu(1,1,3e5+1,1,3e5+1); pre[i]=(pre[i-1]+pre[i])%mod; cout<<pre[i]<<' '<<gc[i]<<' '<<endl; cout<<qu(1,1,3e5+1,1,3e5+1)<<endl; }cout<<endl; }void slv4(){ bd(1,1,3e5+1); nd d[300050]; int gc[300050]; for(int i=1;i<=n;i++) d[i]=(nd){n-i+1,a[i]}; sort(d+1,d+n+1,cmp); SEGTREE.build(1,1,n); for(int i=1;i<=n;i++){ SEGTREE.upd(1,1,n,d[i].id); gc[d[i].id]=SEGTREE.Q(1,1,n,1,d[i].id)*d[i].vl%mod; } for(int i=1;i<=n;i++){ upd2(1,1,3e5+1,1,a[n+1-i]); upd1(1,1,3e5+1,a[n+1-i],gc[i]); suf[i]+=qu(1,1,3e5+1,1,3e5+1); suf[i]=(pre[i-1]+pre[i])%mod; }for(int i=1;i<=n/2;i++){ swap(suf[i],suf[n+1-i]); } } int main(){ freopen("diary.in","r",stdin); freopen("diary.out","w",stdout); cin>>n>>m>>k; for(int i=1;i<=n;i++) scanf("%d",&a[i]); powk[0]=1; for(int i=1;i<=n;i++) powk[i]=1ll*powk[i-1]*k%mod; slv3(); slv4(); while(m--){ int l,r;cin>>l>>r; cout<<(pre[r]-suf[l-1]+mod)%mod<<endl; } return 0; }