#include<bits/stdc++.h> using namespace std; int n,m,k; int ans[2005][2005]; int a[100050],b[100050]; int mod=1e9+7; void cal(int l,int r){ for(int i=l;i<=r;i++) b[i]=a[i]; sort(b+l,b+r+1); int q=1; for(int i=l;i<=r;i++){ q=1ll*q*k%mod; int delta=1ll*q*b[i]%mod; ans[l][r]=(ans[l][r]+delta)%mod; } } int main(){ freopen("diary.in","r",stdin); freopen("diary.out","w",stdout); cin>>n>>m>>k; for(int i=1;i<=n;i++) cin>>a[i]; for(int i=1;i<=n;i++){ for(int j=i;j<=n;j++) cal(i,j); }for(int i=1;i<=n;i++){ for(int j=i;j<=n;j++){ ans[i][j]+=ans[i][j-1]; } } while(m--){ int l,r;cin>>l>>r; int jp8=0; for(int i=1;i<=n;i++){ if(i>r) break; int pr=r,pl=max(l-1,i-1); jp8=(jp8+ans[i][pr]-ans[i][pl])%mod; }cout<<jp8<<endl; } return 0; }