#include<iostream> #include<algorithm> using namespace std; #define int long long const int N=300,P=1000000007; int n,m,k,a[N]; inline int read(){ int i=getchar(),r=0; while(i<'0'||i>'9')i=getchar(); while(i>='0'&&i<='9')r=(r<<1)+(r<<3)+(i^48),i=getchar(); return r; } void init(){ cin>>n>>m>>k; for(int i=1;i<=n;i++)a[i]=read(); } int b[N],f[N][N]; inline int calc(int l,int r){ for(int i=l;i<=r;i++)b[i]=a[i]; sort(b+l,b+r+1); int t=k,res=0; for(int i=l;i<=r;i++){ res=(res+b[i]*t)%P; t=t*k%P; } return res; } signed main(){ // freopen("diary.in","r",stdin); // freopen("diary.out","w",stdout); init(); for(int i=1;i<=n;i++){ for(int j=i;j<=n;j++)f[i][j]=calc(i,j); } for(int T=1;T<=m;T++){ int ans=0; int l,r;cin>>l>>r; for(int i=l;i<=r;i++){ for(int j=1;j<=i;j++){ ans=(ans+f[j][i])%P; } for(int j=r+1;j<=n;j++)ans=(ans+f[i][j])%P; } for(int i=1;i<l;i++)for(int j=r+1;j<=n;j++)ans=(ans+f[i][j])%P; printf("%lld\n",ans); } return 0; }