#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 3e5 + 9, Mod = 1e9 + 7; int n, q, K, a[N]; namespace sub1 { #define ls(u) (u << 1) #define rs(u) (u << 1 | 1) struct seg { int sum[N << 2], lz[N << 2], cnt[N << 2]; void pushup(int u) { sum[u] = (sum[ls(u)] + sum[rs(u)]) % Mod; cnt[u] = cnt[ls(u)] + cnt[rs(u)]; } void pushdown(int u) { sum[ls(u)] = 1ll * sum[ls(u)] * lz[u] % Mod; sum[rs(u)] = 1ll * sum[rs(u)] * lz[u] % Mod; lz[ls(u)] = 1ll * lz[ls(u)] * lz[u] % Mod; lz[rs(u)] = 1ll * lz[rs(u)] * lz[u] % Mod; lz[u] = 1; } void build(int u, int l, int r) { sum[u] = cnt[u] = 0, lz[u] = 1; if (l == r) return; int mid = (l + r) >> 1; build(ls(u), l, mid), build(rs(u), mid + 1, r); } void add(int u, int l, int r, int x, int v) { if (l == r) { (sum[u] += v) %= Mod, cnt[u]++; return; } pushdown(u); int mid = (l + r) >> 1; if (x <= mid) add(ls(u), l, mid, x, v); else add(rs(u), mid + 1, r, x, v); pushup(u); } void upd(int u, int l, int r, int x, int y) { if (x > y) return; if (x <= l && r <= y) { sum[u] = 1ll * K * sum[u] % Mod; lz[u] = 1ll * K * lz[u] % Mod; return; } pushdown(u); int mid = (l + r) >> 1; if (x <= mid) upd(ls(u), l, mid, x, y); if (y > mid) upd(rs(u), mid + 1, r, x, y); pushup(u); } int qry(int u, int l, int r, int x, int y) { if (x <= l && r <= y) return cnt[u]; pushdown(u); int mid = (l + r) >> 1, res = 0; if (x <= mid) res += qry(ls(u), l, mid, x, y); if (y > mid) res += qry(rs(u), mid + 1, r, x, y); return res; } } T; #undef ls #undef rs int ind[N], m, b[N], pw[N], val[1009][1009]; void Main() { pw[0] = 1; for (int i = 1; i <= n; i++) ind[i] = a[i], pw[i] = 1ll * K * pw[i - 1] % Mod; sort(ind + 1, ind + n + 1); m = unique(ind + 1, ind + n + 1) - ind - 1; for (int i = 1; i <= n; i++) b[i] = lower_bound(ind + 1, ind + m + 1, a[i]) - ind; for (int i = 1; i <= n; i++) { T.build(1, 1, m); for (int j = i; j <= n; j++) { int cnt = T.qry(1, 1, m, 1, b[j]); T.add(1, 1, m, b[j], 1ll * a[j] * pw[cnt + 1] % Mod); T.upd(1, 1, m, b[j] + 1, m); val[i][j] = T.sum[1]; } } for (int i = 1; i <= n; i++) { for (int j = i + 1; j <= n; j++) { (val[i][j] += val[i][j - 1]) %= Mod; } } while (q--) { int l, r; scanf("%d%d", &l, &r); int ans = 0; for (int i = 1; i <= r; i++) { ans = ((ll)ans + (val[i][n] - val[i][max(i, l) - 1] + Mod)) % Mod; } printf("%d\n", ans); } } } int main() { scanf("%d%d%d", &n, &q, &K); for (int i = 1; i <= n; i++) { scanf("%d", &a[i]); } sub1::Main(); fclose(stdin); fclose(stdout); return 0; }