#include<bits/stdc++.h> #define up(i,l,r) for(int i=(l);i<=(r);++i) #define down(i,l,r) for(int i=(l);i>=(r);--i) #define p_b push_back #define pi pair<int,int> #define m_p make_pair #define p1 first #define p2 second using namespace std; typedef long long ll; const int V=5e5; const int maxn=1e6+10,mod=1e9+7; inline ll read(){ ll x=0;short t=1; char ch=getchar(); while(ch<'0'||ch>'9'){ if(ch=='-')t=-1;ch=getchar(); }while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); return x*t; } int n,q,K,a[maxn],pw[maxn],pre[maxn],suf[maxn],ret[maxn]; struct node { int len,ret; }; node operator*(node a,node b){ a.len+=b.len; a.ret=(a.ret*1ll*pw[b.len]%mod+b.ret)%mod; return a; } struct SegTree { node d[maxn<<2]; #define ls(p) (p<<1) #define rs(p) (p<<1|1) #define len(p) d[p].len #define ret(p) d[p].ret void pu(int p){ d[p]=d[ls(p)]*d[rs(p)]; } void bd(int l,int r,int p){ len(p)=0; if(l==r){ ret(p)=1;return; } int mid=l+r>>1; bd(l,mid,ls(p)),bd(mid+1,r,rs(p));pu(p); } void B(){ bd(1,n,1); } void upd(int l,int s,int t,int p){ if(s==t){ len(p)++,ret(p)=ret(p)*1ll*K%mod;return; }int mid=s+t>>1; if(l<=mid)upd(l,s,mid,ls(p));else upd(l,mid+1,t,rs(p));pu(p); } node qry(int l,int r,int s,int t,int p){ if(l<=s&&t<=r)return d[p]; int mid=s+t>>1; if(r<=mid)return qry(l,r,s,mid,ls(p)); if(l>=mid+1)return qry(l,r,mid+1,t,rs(p)); return qry(l,r,s,mid,ls(p))*qry(l,r,mid+1,t,rs(p)); } void u(int l){ upd(l,1,n,1); } int g(int l,int r){ return qry(l,r,1,n,1).ret; } #undef ls #undef rs #undef len #undef ret }T; struct SGT { struct node { int lz,sm; node(){ lz=1; } }d[maxn<<2]; #define ls(p) (p<<1) #define rs(p) (p<<1|1) #define lz(p) d[p].lz #define sm(p) d[p].sm void cl(int p,int x){ lz(p)=lz(p)*1ll*x%mod,sm(p)=sm(p)*1ll*x%mod; }void pd(int p){ cl(ls(p),lz(p)),cl(rs(p),lz(p)),lz(p)=1; }void pu(int p){ sm(p)=sm(ls(p))+sm(rs(p));sm(p)%=mod; } void bd(int l,int r,int p){ sm(p)=0,lz(p)=1; if(l==r)return; int mid=l+r>>1; bd(l,mid,ls(p)),bd(mid+1,r,rs(p)); } void B(){ bd(1,V,1); } void upd(int l,int r,int s,int t,int p,int x){ if(l<=s&&t<=r){ cl(p,x);return; }pd(p);int mid=s+t>>1; if(l<=mid)upd(l,r,s,mid,ls(p),x);if(r>=mid+1)upd(l,r,mid+1,t,rs(p),x);pu(p); }void upd2(int l,int s,int t,int p,int x){ if(s==t){ sm(p)=(sm(p)+x)%mod;return; }pd(p);int mid=s+t>>1; if(l<=mid)upd2(l,s,mid,ls(p),x);else upd2(l,mid+1,t,rs(p),x);pu(p); } void u_mul(int l,int r,int x){ upd(l,r,1,V,1,x); }void u_add(int l,int x){ upd2(l,1,V,1,x); }int g(){ return sm(1); } #undef ls #undef rs #undef lz #undef sm }T2; void bd(int *f){ vector<pi>P;P.p_b(m_p(int(-1e9),int(-1e9))); up(i,1,n)P.p_b(m_p(a[i],i));sort(P.begin(),P.end()); T.B();up(i,1,n){ T.u(P[i].p2);ret[P[i].p2]=T.g(1,P[i].p2)*1ll*P[i].p1%mod; }T2.B(); up(i,1,n){ f[i]=f[i-1];int val=ret[i]; T2.u_mul(a[i]+1,V,K); T2.u_add(a[i],val); f[i]+=T2.g();f[i]%=mod; } } void slv(){ n=read(),q=read(),K=read();up(i,1,n)a[i]=read(); pw[0]=1;up(i,1,n)pw[i]=pw[i-1]*1ll*K%mod; bd(pre),reverse(a+1,a+n+1),bd(suf),reverse(suf+1,suf+n+1); while(q--){ int l=read(),r=read(); ll res=pre[n]-pre[l-1]-suf[r+1]; res=(res%mod+mod)%mod; printf("%d\n",res); } } int main(){ slv(); return 0; }