#include <bits/stdc++.h> using namespace std; #define int long long #define lc(x) (x<<1) #define rc(x) (x<<1|1) #define pii pair<int,int> #define p1(x) (x.first) #define p2(x) (x.second) #define endl "\n" const int MXN=300030; const int V=3e5; int pre[MXN],suf[MXN]; int prekrk[MXN],sufkrk[MXN]; int pw[MXN]; const int M=1e9+7; int n,q,k,a[MXN],p[MXN]; inline bool cmp(int x,int y){ if(a[x]==a[y])return x<y; return a[x]<a[y]; } inline bool cmp1(int x,int y){ if(a[x]==a[y])return x>y; return a[x]<a[y]; } inline void add(int &x,int y){ y%=M; x+=y; if(x>=M)x-=M; } inline int qp(int a,int x){ int res=1; while(x){ if(x&1)res=res*a%M; x>>=1; } return res; } struct SGT1s{ int w[MXN<<2],ct[MXN<<2]; inline void upd(int x){ w[x]=(w[lc(x)]+w[rc(x)]*pw[ct[lc(x)]])%M; ct[x]=ct[lc(x)]+ct[rc(x)]; } inline void bd(int x,int l,int r){ if(l==r){ w[x]=1; ct[x]=0; return ; } int mid=l+r>>1; bd(lc(x),l,mid); bd(rc(x),mid+1,r); upd(x); } inline void BD(){bd(1,1,n);} inline void add(int x,int l,int r,int loc){ if(l==r){ct[x]++;w[x]=pw[ct[x]];return ;} int mid=l+r>>1; if(loc<=mid)add(lc(x),l,mid,loc); else add(rc(x),mid+1,r,loc); upd(x); } inline void ADD(int loc){add(1,1,n,loc);} inline pii g(int x,int l,int r,int L,int R){ if(L<=l&&r<=R)return {w[x],ct[x]}; int mid=l+r>>1; pii resl={0,0}; pii resr={0,0}; if(L<=mid)resl=g(lc(x),l,mid,L,R); if(R>mid)resr=g(rc(x),mid+1,r,L,R); return {(p1(resl)+p1(resr)*pw[p2(resl)])%M,p2(resl)+p2(resr)}; } inline int G(int L,int R){return p1(g(1,1,n,L,R));} }T1s; struct SGT1p{ int w[MXN<<2],ct[MXN<<2]; inline void upd(int x){ w[x]=(w[lc(x)]*pw[ct[rc(x)]]+w[rc(x)])%M; ct[x]=ct[lc(x)]+ct[rc(x)]; } inline void bd(int x,int l,int r){ if(l==r){ w[x]=1; ct[x]=0; return ; } int mid=l+r>>1; bd(lc(x),l,mid); bd(rc(x),mid+1,r); upd(x); } inline void BD(){bd(1,1,n);} inline void add(int x,int l,int r,int loc){ if(l==r){ct[x]++;w[x]=pw[ct[x]];return ;} int mid=l+r>>1; if(loc<=mid)add(lc(x),l,mid,loc); else add(rc(x),mid+1,r,loc); upd(x); } inline void ADD(int loc){add(1,1,n,loc);} inline pii g(int x,int l,int r,int L,int R){ if(L<=l&&r<=R)return {w[x],ct[x]}; int mid=l+r>>1; pii resl={0,0}; pii resr={0,0}; if(L<=mid)resl=g(lc(x),l,mid,L,R); if(R>mid)resr=g(rc(x),mid+1,r,L,R); return {(p1(resl)*pw[p2(resr)]+p1(resr))%M,p2(resl)+p2(resr)}; } inline int G(int L,int R){return p1(g(1,1,n,L,R));} }T1p; struct SGT2{ int w[MXN<<2],tg[MXN<<2]; inline void upd(int x){ w[x]=(w[lc(x)]+w[rc(x)])%M; } inline void pd(int x){ if(tg[x]){ w[lc(x)]=w[lc(x)]*pw[tg[x]]%M; w[rc(x)]=w[rc(x)]*pw[tg[x]]%M; tg[lc(x)]+=tg[x]; tg[rc(x)]+=tg[x]; tg[x]=0; } } inline void bd(int x,int l,int r){ tg[x]=0; if(l==r){ w[x]=0; return ; } int mid=l+r>>1; bd(lc(x),l,mid); bd(rc(x),mid+1,r); upd(x); } inline void BD(){ bd(1,1,V); } inline void mod(int x,int l,int r,int loc,int v){ if(l==r){ add(w[x],v); return ; } pd(x); int mid=l+r>>1; if(loc<=mid)mod(lc(x),l,mid,loc,v); else mod(rc(x),mid+1,r,loc,v); upd(x); } inline void MOD(int loc,int v){ mod(1,1,V,loc,v); } inline void mod(int x,int l,int r,int L,int R,int p){ if(L<=l&&r<=R){ w[x]=w[x]*pw[p]%M; tg[x]+=p; return ; } pd(x); int mid=l+r>>1; if(L<=mid)mod(lc(x),l,mid,L,R,p); if(R>mid)mod(rc(x),mid+1,r,L,R,p); upd(x); } inline void MOD(int L,int R,int p){if(R<=V&&L<=R)mod(1,1,V,L,R,p);} inline int G(){return w[1];} }T2; signed main(){ ios::sync_with_stdio(0); // freopen("diary.in","r",stdin); // freopen("diary.out","w",stdout); scanf("%lld%lld%lld",&n,&q,&k); pw[0]=1; for(int i=1;i<MXN;i++)pw[i]=pw[i-1]*k%M; for(int i=1;i<=n;i++){ scanf("%lld",&a[i]); p[i]=i; } sort(p+1,p+n+1,cmp); T1p.BD(); for(int i=1;i<=n;i++){ int x=p[i]; prekrk[x]=T1p.G(1,x); T1p.ADD(x); } T1s.BD(); sort(p+1,p+n+1,cmp1); for(int i=1;i<=n;i++){ int x=p[i]; sufkrk[x]=T1s.G(x,n); T1s.ADD(x); } T2.BD(); for(int i=1;i<=n;i++){ T2.MOD(a[i]+1,V,1); T2.MOD(a[i],a[i]*prekrk[i]%M); pre[i]=T2.G(); } T2.BD(); for(int i=n;i>=1;i--){ T2.MOD(a[i]+1,V,1); T2.MOD(a[i],a[i]*sufkrk[i]%M); suf[i]=T2.G(); } for(int i=1;i<=n;i++) pre[i]=(pre[i]+pre[i-1])%M, suf[i]=(suf[i]+suf[i-1])%M; for(int i=1;i<=q;i++){ int l,r; scanf("%lld%lld",&l,&r); printf("%lld\n",(suf[r]-pre[l-1]+M)*k%M); } cout.flush(); fflush(stdout); return 0; }